博文中会简要介绍Leetcode P0198题目分析及解题思路。

“House Robber”是一道比较简单的动态规划问题，其实也是一道原型题。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

这道题的思路很简单，这里就直接放上递推表达式，

令dp[i]表示前i个房屋可以得到的最大资金

dp[0] = 0
显然如果不抢劫，那么得到的资金为零

dp[1] = nums[0]
如果只抢劫一个房子，那么能获得的最大资金显然是第一个房子拥有的资金数目

dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
对于第i个房子有两种可能的情况，一种是不抢第i个房子，那么此时前i个房子能获得的资金就等于前i-1个房子能获得的最大资金；另一种是抢第i个房子，那么由于不能抢劫相邻的两个房子，那么此时前i个房子能获得的资金就等与抢前i-2个房子能获得的最大资金再加上第i个房子能获得的资金。

最终前i个房子能获得的最大资金dp[i]就等于这两种情况中的较大者。

根据上述的递推表达式，我们能够很容易的得到动态规划的解法和代码。

以下是Java的题解代码实现。

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

以下是C++的题解代码实现。

class Solution {
public:
    int rob(vector<int>& nums) {
        int N = nums.size();
        if (N == 0)
            return 0;
        
        int *dp = new int[N+1];
        
        dp[0] = 0;
        dp[1] = nums[0];
        
        // DP
        for (int i1=2; i1<=N; ++i1) {
            dp[i1] = max(dp[i1-1], dp[i1-2]+nums[i1-1]);
        }
        
        return dp[N];
    }
};