✕
![preview]()
新鲜事
原文
打家劫舍（House Robber）
你有一只叫老花的三花小猫，它今天要在厨房里偷吃
-故事开始
厨房里摆着一排6个零食罐子，每个罐子里零食的数量分别是
[2,5,3,1,6,4]
老花知道，不能连续偷两个挨着的罐子，不然会被发现
它想：最多能偷到多少呢？
-老花灵动的小脑袋开始思考
老花蹲在第一个罐子面前，它认为有两个选择
选择A：偷这个罐子
得到：2块
代价：下一个罐子不能偷了（得跳到下下个）
接下来能偷的最大值：从第3个罐子开始的最优方案
选择B：不偷这个罐子
得到：0块
好处：下一个罐子可以偷！
接下来能偷的最大值：从第2个罐子开始的最优方案
-回忆
主人对老二（也是一只三花）说过“站在第 i 个罐子面前，你能偷到的最多零食=max(偷这个+从i+2开始能偷的， 不偷这个+从i+1开始能偷的)”
还是不懂……什么意思呢？
-倒着走
位置 i 零食值 nums[i] dp[i]（从i开始能偷的最大值）
6 4 dp[6]=4
5 6 dp[5]=max(6,4)=6
4 1
dp[4]=max(1+dp[6],dp[5])=max(1+4, 6)=6
3 3 dp[3]=max(3+dp[5],dp[4])=max(3+6, 6)=9
2 5 dp[2]=max(5+dp[4],dp[3])=max(5+6, 9)=11
1 2 dp[1]=max(2+dp[3],dp[2])=max(2+9, 11)=11
老花明白了，最多能偷到11块
-老花的总结
原来动态规划就是站在现在，想想未来，然后选一个最好的！
dp[i]=max(
nums[i]+dp[i+2], // 偷当前的，跳到下下个
dp[i+1] // 不偷当前的，看下一个
)
