LeetCode198. 打家劫舍

思路

动规五部曲

1.定义dp数组

dp[j]表示：前j个元素的最大价值为dp[j]；

2.递推公式

dp[j]=Math.max(dp[j-2]+nums[j],dp[j-1]);

因为不能取相邻的物品，所以如果要取第j个物品，只能是取了j-2之后。所以递推公式就可以得到上式。

3.初始化

由递推公式可以知道dp[0]=nums[0];

dp[1]=nums[0]和nums[1]中最大的一个。

4.遍历顺序

根据递推公式可以知道应该是正序遍历。

5.打印顺序

dp数组的最后一个值就是最后的结果。

代码

class Solution {    public int rob(int[] nums) { int dp[] = new int[nums.length]; dp[0]=nums[0]; if(nums.length == 1){     return nums[0]; } dp[1] = Math.max(nums[0],nums[1]); for(int j =2;j<nums.length;j++){   dp[j]=Math.max(dp[j-2]+nums[j],dp[j-1]); } return dp[nums.length-1];    }}