动态规划算法解题思路

在做动态规划类题目时最大的感觉就是能够分析出这道题目需要用动态规划算法来解，却没有办法构建出解题步骤，看到别人的分析时候又感觉代码很简单但是自己却想不出。
其实这还是没有理解到动态规划算法的基本思想。

这里我们通过一道例题来进行分析

由于相邻房屋不能偷，如果我们从前往后思考当我们偷第一家那么我们就不能偷第二家，如果我们偷第二家我们就不能偷第三家…这时发现我们每走一步问题都为发生改变。
此时我们就应该换个角度思考从后往前看：
假如我们现在有5家房屋
当我们选择偷第五家的时候，那么最大金额 = 第五家金额 + 前三家偷窃的最优解。
当我们不偷第五家的时候，那么最大金额 = 前四家偷窃的最优解。

这时候我们就能明白:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择。
这道题最主要的部分就是要分析出每一步的最优解然后往后递推。

我们来结合示例2进行分析：
输入为：[2，7，9，3，1]
我们使用一个dp[]数组储存我们没阶段的最优解

(1)假设起始状态下没有房屋时最优解为：0
dp[0]=0(可以看作0房屋时候的最优解)
(2)如果只存在第一家的时候那么最优解为：2
dp[1]=2（1间房屋时候的最优解）
(3)如果存在两家的时候最优解就是：7
dp[2]=7（2间房屋时候的最优解）
(4)如果存在三家的时候最优解就是：11
这里不难看出，当我们选择偷第三家的时候：
最大金额 = dp[1]（前一家的最优解) + nums[2]（第三家的金额）
不偷第三家的时候：
最大金额 = dp[2] （前两家的最优解）
然后我们比较这两种情况，金额最大就作为前三家的最优解
即dp[3]=11（dp[1]+nums[2] > dp[2]）
(4)如果存在四家的时候最优解就是：11
dp[4]=11 （dp[2]+nums[3] < dp[3]）
(5)如果存在五家的时候最优解就是：12
dp[5]=12 （dp[3]+nums[4] > dp[4]）

所以我们经过分析后就能够得出状态转移方程为：
dp[n] = MAX(dp[n-2] + nums[n-1], dp[n-1])

题解代码：

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

本文地址：https://blog.csdn.net/dekulugu/article/details/108572140