0198.house-robber

Spread the love

我的思路 就是用动态规划的思路填表,

假设会去第一间房子,然后如果和第二间房子进行比较,如果第二间大,谁就是真正意义的参照物。因为从第三间开始就要计算,1+3和2谁大的问题。scoretable[i-2]代表上一间没偷的值

但是太过于复杂,一不小心就错了

参考答案的思路,dp[i] = Math.max(dp[i – 2] + nums[i – 2], dp[i – 1]);

更直观的解释:指针一负责找王储,指针二找国王。王储和国王不能连任

因为动态规划的特点,比如指针在i,i-1是最优解,i-2是次最优解,i只能和次最优解合并

比如在

[2,7,9,3,1]

王储先储备2,如果7大于2,王储不变,7作为国王,

读到9的时候,国王的计算公式是 max(当前数字+王储,国王),可以看到2+9>7,所以11列为国王,7变成王储。读到3时候,max(3+7,11),所以王储是10,11是国王;但是他们不能连任,所以11是王储,10是国王。最后读到1的时候,max(1+11,10),国王变成12是答案

This entry was posted in leetcode. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *