《动态规划》刷题训练

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

题目解析

动态规划问题的特点：

• 问题可以被划分为若干重叠子问题
• 子问题可以通过已知的子问题求解，且子问题可以重复利用
• 需要一个数据结构来存储子问题的解，以便在使用时取出

为什么这题能够使用动态规划？

• 重叠子问题：
  设总共有$n$家房屋，原问题则为有$n$家房屋时所能偷窃到的最大金额。
  该问题能够划分为成若干重叠子问题：有$k(k=1\dots \dots n?1)$家房屋时能够偷窃到的最大金额
• 子问题可以通过求解的子问题求解：
  有$k$家房屋时，能够偷窃的最大金额：
  • 第$k$家不偷窃时，最大金额 = 当房屋为$k?1$时，最大偷窃的金额
  • 第$k$家偷窃时，最大金额 = 第$k?1$不偷窃时，最大金额 + 第$k$家房屋能偷的钱= 当房屋为$k?2$时，最大偷窃的金额 + 第$k$家房屋能偷的钱

解题步骤：

• 将原问题转化为一个或多个子问题
• 定义问题的状态转移方程
• 设置边界条件
• 计算子问题的解并记录
• 由子问题的解得到原问题的解

• 问题【当有$k$家房屋时，被偷窃最大的金额】可划分为(从左向右看)：
  • 第$k$家不偷窃时，最大金额
  • 第$k$家偷窃时，最大金额
• 状态转移方程：
  • 子问题为【第$k$家不偷窃时，最大金额】：
    第$k$家不偷窃，那么第$k$家肯定不会构成相邻的非法条件。此时可以当第$k$家不存在，所以问题变成：【房屋数量为$k?1$时的最大偷窃金额】
  • 子问题为【第$k$家偷窃时，最大金额】：
    此时第$k?1$家肯定不能进行偷窃，否则会触发报警器。因此第$k?1$家的状态只能是不偷窃，所以问题变成：【第$k$家偷、第$k?1$家不偷时，最大金额】
    状态转移方程：
    

此时，我们定义一个二维数组$dp[n][2]$来存储子问题的解：

$n$表示一共有$n$个重叠子问题

$dp[k][0]$表示：房屋数量为$k$时，且第$k+1$家不偷窃时最大的偷窃金额
$dp[k][1]$表示：房屋数量为$k$时，且第$k+1$家偷窃时最大的偷窃金额

设问题【当有$k$家房屋时，最大得偷窃金额】表示为$f(k)$，根据上面的等式，此时$f(k)$可表示成两个子问题：
$$f(k)=\{\begin{array}{ll}f(k?1)& k不偷\\ nums(k)+dp[k?1][0]& k偷\end{array}$$

$f(k?1)$分别有 第$k?1$家偷 和 第$k?1$家不偷下对应的解，我们取最大即可：
f ( k ? 1 ) = M A X { d p [ k ? 1 ] [ 0 ] , d p [ k ? 1 ] [ 1 ] } f(k-1)=MAX\{dp[k-1][0],dp[k-1][1]\} f(k?1)=MAX{dp[k?1][0],dp[k?1][1]}

最终状态转移方程，可得：
f ( k ) = { M A X { d p [ k ? 1 ] [ 0 ] , d p [ k ? 1 ] [ 1 ] } k 不偷 n u m s ( k ) + d p [ k ? 1 ] [ 0 ] k 偷 f(k)=\begin{cases} MAX\{dp[k-1][0],dp[k-1][1]\} & k不偷 \\ nums(k) +dp[k-1][0] & k偷 \end{cases} f(k)={MAX{dp[k?1][0],dp[k?1][1]}nums(k)+dp[k?1][0]?k不偷k偷?

• 边界条件，当$k=0$的时候，表示第$k+1=1$家的情况：
  • 第$1$家=不=偷：$dp[0][0]=0$
  • 第$1$家偷：$dp[0][1]=nums[0]$

从状态转移方程看，我们需要从左到右的更新dp数组。

最后，附上Java实现方式：

class Solution {
    public int rob(int[] nums) {
    	//len表示有几家房子
        int len = nums.length;
		
		//定义dp数组存储子问题的解，原问题的解存储在dp[len-1]中
        int dp[][] = new int[len][2];
		
		//边界条件
        dp[0][0] = 0;//第一家不偷
        dp[0][1] = nums[0];//第一家偷

		//从左到右依次更新
        for(int i=1;i<len;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0]+nums[i];
        }
        return Math.max(dp[len-1][0],dp[len-1][1]);
    }
}