在某个遥远的国度里,有一种传统的游戏叫做“跳跳棋”,这是一种基于积分的游戏。在这个国度里,跳跳棋已经有着悠久的历史,并且已经被许多人认为是一种智力和策略的游戏。人们在跳跳棋中可以锻炼自己的思维和判断能力。因此,这个游戏非常受欢迎,人们经常在闲暇时间里玩这个游戏。
题目抽象一下变成从数组中选出若干个不相邻的数,让这些数总和最大。
直接使用动态规划解决,dp[i] 代表只考虑前 i 个数得到的最大值,因为不能选相邻的数,所以 dp[i]=max(dp[i−1],dp[i−2]+a[i]), dp[n] 就是最后的答案,发现 a[i] 并不需要存下来,边更新边读入即可。
C++代码
扫码备注加群即可,期待您的到来~