198. House Robber

序列型动态规划
• 状态 State
• f[i] 表示前i个房子中,偷到的最大价值
•方程 Function
• f[i] = 1. A[i-1] + max(f[i-2]....f[1]) 偷第i个房子
           2. f[i-1] 不偷第i个房子 总结为
• f[i] = max(f[i-1], f[i-2] + A[i-1]);
• 初始化 Intialization
   f[0] = 0;
   f[1] = A[0];
• 答案 Answer • f[n]

这里节省空间可以用滚动数组,只需要大小为2的数组就行。下图是一个滚动数组的演示。

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array