题解 | #不相邻取数#

根据题意，本题与"打家劫舍"的思路很相似，按照动态规划的思路，建立 dp 数组，赋初值，然后根据转移方程进行迭代；由于选取的数字是不相邻的数字，则 dp[i] 与 dp[i - 1] 和 dp[i - 2] + data[i] 有关，初始值 dp[0] = data[0], 动态规划数组每次进行状态转移只与本次相关状态有关，无需考虑之前的值。 自顶向下的状态转移方式代码如下：

n = int(input().strip())
data = list(map(int, input().strip().split()))
dp = [0 for _ in range(n)]
for i in range(n):
    dp[i] = data[i]
    if i >= 1:
        dp[i] = max(dp[i - 1], dp[i])
    if i >= 2:
        dp[i] = max(dp[i - 2] + data[i], dp[i - 1])
print(dp[-1])

自底向上的状态转移方式代码如下：

n = int(input().strip())
data = list(map(int, input().strip().split()))
dp = [0 for _ in range(n + 2)]
for i in range(n - 1, -1, -1):
    dp[i] = max(dp[i + 1], data[i] + dp[i + 2])
print(dp[0])