刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

地宫宝藏

编程实现：

现有地宫里埋藏着一些宝藏，已知地宫的藏宝房间有n间，且呈环形分布，每个房间都有一定价值的宝藏，由于机关设置，你每取走一个房间的宝藏，相邻房间的房门就会锁死，不能再进入，给出房间的数量n和每个房间的宝藏价值，请问你最多能拿走多少价值的宝藏？

输入描述

第一行输入一个正整数n，表示地宫有n个房间（1≤n≤100）。

第二行输入n个正整数，表示每个房间的宝藏价值（1≤宝藏价值≤100）。

输出描述

输出最多可以获得的宝藏价值。


输入样例

4
10 3 7 13

输出样例

17

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythonn = int(input())values = list(map(int, input().split()))dp = [0] * ndp[0] = values[0]max_value = values[0]for i in range(1, n):dp[i] = max(dp[i-1], values[i] + dp[i-2])max_value = max(max_value, dp[i])print(max_value)```

解析：

【喵呜刷题小喵解析】：

这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[i]表示从第0个房间到第i个房间可以获得的最大宝藏价值。

对于每个房间i，我们可以选择拿或者不拿。如果选择拿，那么dp[i]就等于dp[i-1]加上当前房间的宝藏价值；如果选择不拿，那么dp[i]就等于dp[i-1]。因此，dp[i]的最大值应该是dp[i-1]和dp[i-1]+values[i]中的较大值。

由于房间是环形的，我们需要额外处理一下首尾相连的情况。我们可以分别计算不拿第0个房间和拿第0个房间两种情况下的最大宝藏价值，然后取两者中的较大值作为最终结果。

最终的时间复杂度是O(n)，空间复杂度也是O(n)。
创作类型：
原创

本文链接：地宫宝藏 编程实现： 现有地宫里埋藏着一些宝藏，已知地宫的藏宝房间有n间，且呈环形分布，每个房间都有

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share