198. 打家劫舍--动态规划

题目:

思路:

动态规划的的四个解题步骤是：

• 定义子问题
• 写出子问题的递推关系
• 确定 DP 数组的计算顺序
• 空间优化（可选）

该思路来自于leetcode上一个老哥写的非常详细的动态规划思路,可以看原文

代码:

class Solution {
        //f(k)=max(f(k-1),(f(k-2)+curr))
        public int rob(int[] nums) {
            if (nums.length==0){
                return 0;
            }
            final int length = nums.length;
            int[] money=new int[length+1];
            money[0]=0;
            money[1]=nums[0];
            for (int i = 2; i <= length; i++) {
                money[i]=Math.max(money[i-1],(money[i-2]+nums[i-1]));
            }

            return money[length];
        }
    }

空间优化后代码:

空间优化是动态规划问题的进阶内容了。对于初学者来说，可以不掌握这部分内容。

空间优化的基本原理是，很多时候我们并不需要始终持有全部的 DP 数组。对于小偷问题，我们发现，最后一步计算 f(n)f(n) 的时候，实际上只用到了 f(n-1)f(n−1) 和 f(n-2)f(n−2) 的结果。n-3n−3 之前的子问题，实际上早就已经用不到了。那么，我们可以只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。

class Solution {
        //f(k)=max(f(k-1),(f(k-2)+curr))
        public int rob(int[] nums) {
            if (nums.length==0){
                return 0;
            }
            final int length = nums.length;
            int ppre=0,pre=nums[0], curr=nums[0];
            for (int i = 2; i <= length; i++) {
                curr =Math.max(pre,(ppre+nums[i-1]));
                ppre=pre;
                pre= curr;
            }

            return curr;
        }
    }