动态规划（1）

淩亂°似流年 2022-12-15 15:27 218阅读 0赞

**转自**：http://cppblog.com/menjitianya/archive/2015/10/23/212084.html

**建议去支持原文**

**目录  **

**一、动态规划初探**

1.  递推
    
    1.  等差数列、等比数列
    2.  经典：斐波那契数列
        
        **斐波那契数列**指的是这样一个数列：  
        ![20201105101116891.png][]
        
         
        
        这个数列从第3项开始，每一项都等于前两项之和。
        
        1.  相关数学：
            
            1.  排列组合
            2.  兔子繁殖问题
    3.   
2.  记忆化搜索
3.  状态和状态转移
4.  最优化原理和最优子结构
5.  决策和无后效性

**二、动态规划的经典模型**

1.  线性模型
2.  区间模型
3.  背包模型
4.  状态压缩模型
5.  树状模型

**三、动态规划的常用状态转移方程**

1.  1D/1D
2.  2D/0D
3.  2D/1D
4.  2D/2D

**四、动态规划和数据结构结合的常用优化**

1.  滚动数组
2.  最长单调子序列的二分优化
3.  矩阵优化
4.  斜率优化
5.  树状数组优化
6.  线段树优化
7.  其他优化

**五、动态规划题集整理**

### 一.线性DP经典问题 ###

[198. 打家劫舍][198.]

**以下文字来源：原答案的第二个**

如果你对于动态规划还不是很了解，或者没怎么做过动态规划的题目的话，那么 House Robber （小偷问题）这道题是一个非常好的入门题目。本文会以 House Robber 题目为例子，讲解动态规划题目的四个基本步骤。

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

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

下面我们一步一步地进行讲解。

**步骤一：定义子问题**

稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题？子问题是和原问题相似，但规模较小的问题。例如这道小偷问题，原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。

![小偷问题的子问题定义][044fb25be7258eb18fd3bd85171a22da.png]

可以看到，子问题是参数化的，我们定义的子问题中有参数 k。假设一共有 n 个房子的话，就一共有 n个子问题。动态规划实际上就是通过求这一堆子问题的解，来求出原问题的解。这要求子问题需要具备两个性质：

*  原问题要能由子问题表示。例如这道小偷问题中，k=n 时实际上就是原问题。否则，解了半天子问题还是解不出原问题，那子问题岂不是白解了。
 *  一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中，f(k)可以由 f(k-1)和 f(k-2) 求出，具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。

小偷问题由于比较简单，定义子问题实际上是很直观的。一些比较难的动态规划题目可能需要一些定义子问题的技巧。

**步骤二：写出子问题的递推关系**

这一步是求解动态规划问题最关键的一步。然而，这一步也是最无法在代码中体现出来的一步。在做题的时候，最好把这一步的思路用注释的形式写下来。做动态规划题目不要求快，而要确保无误。否则，写代码五分钟，找 bug 半小时，岂不美哉？

我们来分析一下这道小偷问题的递推关系：  
![20210409113243456.png][]

![子问题的递推关系][60062341c29f5358bd749ee4061a0c19.png]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70][]

**步骤三：确定 DP 数组的计算顺序**

在确定了子问题的递推关系之后，下一步就是依次计算出这些子问题了。在很多教程中都会写，动态规划有两种计算顺序，一种是自顶向下的、使用备忘录的递归方法，一种是自底向上的、使用 dp 数组的循环方法。不过在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的 dp 数组。

DP 数组也可以叫”子问题数组”，因为 DP 数组中的每一个元素都对应一个子问题。如下图所示，dp\[k\] 对应子问题 f(k)，即偷前 kk 间房子的最大金额。

![DP 数组与子问题的对应关系][DP]

那么，只要搞清楚了子问题的计算顺序，就可以确定 DP 数组的计算顺序。对于小偷问题，我们分析子问题的依赖关系，发现每个 f(k)依赖 f(k-1) 和 f(k-2)。也就是说，dp\[k\] 依赖 dp\[k-1\] 和 dp\[k-2\]，如下图所示。

![DP 数组的依赖顺序][DP 1]

那么，既然 DP 数组中的依赖关系都是向右指的，DP 数组的计算顺序就是从左向右。这样我们可以保证，计算一个子问题的时候，它所依赖的那些子问题已经计算出来了。

确定了 DP 数组的计算顺序之后，我们就可以写出题解代码了：

public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题：
        // f(k) = 偷 [0..k) 房间中的最大金额
    
        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
    
        int N = nums.length;
        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int k = 2; k <= N; k++) {
            dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
        }
        return dp[N];
    }

**步骤四：空间优化**

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

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

这样一来，空间复杂度也从 O(n)降到了 O(1)。优化后的代码如下所示：

public int rob(int[] nums) {
        int prev = 0;
        int curr = 0;
    
        // 每次循环，计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
        }
    
        return curr;
    }

### 二.打家劫舍2 ###

public static void main(String[] args) {
    		int[] money = {5,4,3,2,1,10};
    		System.out.println(getMaxMoney2(money));
    	}
    	/*你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
    
    	给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
    
    	 
    
    	示例 1：
    
    	输入：[1,2,3,1]
    	 
    	输出：4
    	解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
    	     偷窃到的最高金额 = 1 + 3 = 4 。*/
    	private static Integer getMaxMoney(int[] money) {
    		int N = money.length;
    		if(N ==0) {
    			return 0;
    		}
    		if(N == 1) {
    			return money[1];
    		}
    		// 子问题：偷0-k的房间的最大金额
    		// f(0) = 0
    		// f(1) = money[0]
    		// f(k) = Math.max(f(k-1),f(k-2)+f(k))
    		
    		int[] dp = new int[N+1];
    		dp[0]=0; // 0
    		dp[1]=money[0]; // 1
    		for(int i=2; i<=N; i++) {
    			dp[i] = Math.max(dp[i-1], dp[i-2]+money[i-1]);
    			System.out.println(dp[i]);
    		}
    		
    		return dp[N];
    	}
    	
    	private static Integer getMaxMoney2(int[] money) {
    		int N = money.length;
    		if(N ==0) {
    			return 0;
    		}
    		if(N == 1) {
    			return money[1];
    		}
    		// 子问题：偷0-k的房间的最大金额
    		// f(0) = 0
    		// f(1) = money[0]
    		// f(k) = Math.max(f(k-1),f(k-2)+f(k))
    		
    		int[] dp1 = new int[N];
    		dp1[0]=0; // 0
    		dp1[1]=money[0]; // 1
    		for(int i=2; i<=N-1; i++) {
    			dp1[i] = Math.max(dp1[i-1], dp1[i-2]+money[i-1]);
    			System.out.println(dp1[i]);
    			System.out.println(JSON.toJSONString(dp1));
    			System.out.println("-----------");
    		}
    
    		System.out.println("***************");
    		
    		int[] dp2 = new int[N];
    		dp2[0]=0; // 0
    		dp2[1]=money[1]; // 1
    		for(int i=2; i<=N-1; i++) {
    			dp2[i] = Math.max(dp2[i-1], dp2[i-2]+money[i]);
    			System.out.println(dp2[i]);
    			System.out.println(JSON.toJSONString(dp2));
    			System.out.println("-----------");
    		}
    		System.out.println("***************");
    		int max = Math.max(dp1[N-1], dp2[N-1]);
    		
    		return max;
    	}

[20201105101116891.png]: /images/20221123/98ff8037010f476dbaba850dcbeda4b8.png
[198.]: https://leetcode-cn.com/problems/house-robber/
[044fb25be7258eb18fd3bd85171a22da.png]: /images/20221123/4ec018a11a794566ac1549e9edb20bd8.png
[20210409113243456.png]: /images/20221123/d6fcbe29965947cdaf31cec1a02f0999.png
[60062341c29f5358bd749ee4061a0c19.png]: /images/20221123/681a8ad04aed4695b47d51df674e70e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70]: /images/20221123/59b759e7017446a7ab41e057f654c039.png
[DP]: /images/20221123/772082a9730c4202b058dfe7353dfb76.png
[DP 1]: /images/20221123/274417be71a949a89d8e52a470a83976.png