今日题目：打家劫舍（经典动态规划题目）

题目描述如下：

这是一道关于动态规划的简单题，虽说是简单题，但是关于动态规划的，看起来就有点恐惧，但看到这道题是简单题，顿时就觉得“天晴了，雨停了，我觉得我又行了”，然后就开始想关于他地动态递推公式，我一开始地想法是（由于题目要求小偷不能同时偷相邻两个房屋，所以我觉得递归公式是dp[i] = dp[i-2]+nums[i]），然后很快就写出了程序，可是提交地时候却没有通过

最后还是没办法只有去看了题解：

看来还是我理解的有问题，它的递推公式应该是dp[i] = max(dp[i-2]+nums[i],dp[i-1])，总结来说我之所以会得出错误的递推公式，还是对于动态规划的思想理解的不到位，这里面的动态递推关系应该是每一步存的都是到达那一步的时候所能偷窃到的最大金额数（而我当时想的是小偷到达那个房子时偷窃的金额数，并没有考虑是否最大）。

下面就是实现代码了：

class Solution {

    public int rob(int[] nums) {

        int[] dp = new int[nums.length];

        if(nums.length==0)return 0;

        if(nums.length==1)return nums[0];

        if(nums.length==2) return nums[0]>nums[1]?nums[0]:nums[1];

        dp[0] = nums[0];

        dp[1] = Math.max(nums[0],nums[1]);

        int max = nums[0]>nums[1]?nums[0]:nums[1];

        for(int i=2;i<nums.length;i++){

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

            if(max<dp[i])

                max = dp[i];

        }

        return max;

    }

}