动态规划系列汇总，持续更新！

迈不过友情╰ 2022-11-18 02:11 218阅读 0赞

### 文章目录 ###

*   *  一、动态规划介绍
     *  二、高频题型汇总
     *   *  2.1 爬楼梯
         *   *  题目
             *  解析
         *  2.2 最大子序和
         *   *  题目
             *  解析
         *  2.3 最长递增子序列
         *   *  题目
             *  解析
         *  2.4 最小路径和
         *   *  题目
             *  解析
         *  2.5 按摩师
         *   *  题目
             *  题解
         *   本文将持续更新，欢迎大家点赞收藏！

## 一、动态规划介绍 ##

动态规划 Dynamic Programming，简称 **DP**，是运筹学的一个分支，它是解决**多阶段决策过程**最优化的一种数学方法。其**核心思想**是：把多阶段问题变换为一系列**相互联系**的的单阶段问题，然后逐个加以解决。概念中的**相互联系**，在实际问题中， 需要我们自己提炼，并以**状态转移方程**的形式给出。

很多人觉得DP难，根本原因是因为DP跟一些有固定套路的算法不同（比如DFS、二分法、KMP），它没有实际的步骤规定第一步、第二步来做什么，所以准确来说，DP其实是一种解决问题的思想。

***为了大家能一步步深入了解动态规划，本文选取了一些大厂笔试中考察频率较高的题型。题目难度由浅入深，后续会逐渐补充整理，欢迎大家点赞收藏，评论交流！***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]

--------------------

## 二、高频题型汇总 ##

### 2.1 爬楼梯 ###

#### 题目 ####

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    注意：给定 n 是一个正整数。
    
    示例 1：
    输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶
    
    示例 2：
    输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/climbing-stairs
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 解析 ####

**思路一：通过单阶段之间的关系确定状态转移方程**

当做这个题是，我们可以先简单推演一下。由于一次只能上1个或2个台阶，不难发现，**假如我当前在第n个台阶上，那么我上一次应该在第n-1个或者第n-2个台阶上**。换句话说，当我知道到达第n-1个台阶的方案数f(n-1)，到达第n-2个台阶的方案数是f(n-2)。

那么，我们就自然知道到达第n个阶梯时的方案数，即：**f(n)=f(n-1)+f(n-2)**，这也被称为此问题的**状态转移方程**。

当然，我们还需要确定状态转移方程的**边界条件**。即几种特殊情况：**f(0)=0，f(1)=1，f(2)=2；**

确定好状态转移方程和边界条件后，就可以开始敲代码了：

class Solution { 
    public:
        int climbStairs(int n) { 
            int ans = 0;
            if(n==0)
                return 0;
            else if(n==1)
                return 1;
            else if(n==2)
                return 2; 
            else
                return climbStairs(n-1)+climbStairs(n-2);
        }
    };

这是一个不断的迭代过程，在实际的提交过程中，很可能超过时间限制。

**思路二：数学归纳法**

如果觉得很难直接去找到单阶段问题间的关系，也换一种思考方式。通过数学归纳法来推理出隐藏的状态转移方程。

在不清楚单阶段之间的关系的时候，可以正向推演一遍，可以得到如下表所示的数据：

通过观察f(n)的变换，想必大家已经看出了规律。即，前两数之和为第三数的值。

由此，我们就可以写代码啦：

class Solution { 
    public:
        int climbStairs(int n) { 
            int f1=0, f2=1, ans=2;//初始化
            if(n==1)
                return 1;
            else if(n==2)
                return 2;
            else{ 
                for(int i=1; i<n-1; ++i){ 
                    f1 = f2;
                    f2 = ans;
                    ans = f1 + f2;
                }
            return ans;
            }
        }
    };

代码提交结果：  
![d8351ed24c637db3fef0eef05348f356.png][]

--------------------

### 2.2 最大子序和 ###

#### 题目 ####

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    
    示例 1：
    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
    
    示例 2：
    输入：nums = [1]
    输出：1
    
    示例 3：
    输入：nums = [-1]
    输出：-1
    
    提示：
    1 <= nums.length <= 3 * 10^4
    -10^5 <= nums[i] <= 10^5

#### 解析 ####

假设 nums 数组的长度是 n，下标从 0 到 n-1。我们用 dp\[i\] 代表以第 i 个数结尾的**连续子数组的最大和**，那么很显然我们要求的答案就是： m a x ( d p \[ i \] ) , i ∈ \[ 0 , n − 1 \] max(dp\[i\]), i\\in\[0, n-1\] max(dp\[i\]),i∈\[0,n−1\]

因此，关键点就是要找出dp\[i\]与dp\[i-1\]的关系，从而构建状态转移方程。进一步分析可知：

*  当dp\[i-1\]>0时，dp\[i\] = dp\[i-1\] + nums\[i\]
 *  当dp\[i-1\]<0时，dp\[i\] = nums\[i\]

C++实现如下：

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            int max_cur = nums[0]; //初始化当前最大dp[i]
            int max_all = nums[0]; //初始化全局最大值
            for(int i=1; i<nums.size(); ++i){ 
                if(max_cur>0)
                    max_cur = max_cur + nums[i];
                else
                    max_cur = nums[i];
                max_all = max(max_all, max_cur);
            }
            return max_all;
        }
    };

代码提交结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

--------------------

### 2.3 最长递增子序列 ###

在上一题中，我们了解了什么是DP（动态规划），并且通过DP中的经典问题 “最大子序和”，学习了状态转移方程应该如何定义。本题我们将沿用之前的分析方法，通过一道例题，进一步巩固之前的内容！

#### 题目 ####

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
    子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
    
    示例 1：
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    
    示例 2：
    输入：nums = [0,1,0,3,2,3]
    输出：4
    
    示例 3：
    输入：nums = [7,7,7,7,7,7,7]
    输出：1

#### 解析 ####

**假定 dp\[i\] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，其中，nums\[i\]必须被选取。**

我们从小到大计算 dp 数组的值，在计算 dp\[i\] 之前，我们已经计算出 dp\[0\]、dp\[1\]、… 、dp\[i-1\] 的值。

对于一个任意数组 nums = \[1, 8, 5, 6, 9, 1\]。我们可以分两种情况讨论：

*  当nums\[i\]比前面的元素都小，那么 **dp\[i\] = 1**
 *  如果nums\[i\]前面存在比它小的元素nums\[j\]，0<j<i。那么 **dp\[i\] = max(dp\[j\]) + 1**

最后，整个数组nums的最长递增子序列长度为：max(dp\[i\])，0<i<nums.size()

C++代码实现如下：

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
    
            int len = nums.size();
            if(!len) return 0;
    
            vector<int> dp(len, 0);
            int ans = 0;
            
            for(int i=0; i<len; ++i){ 
                dp[i] = 1;
                for(int j=0; j<i; ++j){ 
                    if(nums[i]>nums[j])
                       dp[i]=max(dp[i], dp[j]+1);
                }
                ans = max(ans, dp[i]);
            }
            return ans;
        }
    };

*  时间复杂度分析：O(n^2)，其中n为数组nums的长度。
 *  空间复杂度分析：O(n)，需要额外使用长度为n的dp数组。

--------------------

> 这里是一段防爬虫文本，请读者忽略。 本文原创首发于 CSDN，作者【AI 菌】。  
> 博客首页：[https://blog.csdn.net/wjinjie][https_blog.csdn.net_wjinjie]  
> 本文链接：[https://ai-wx.blog.csdn.net/article/details/115610626][https_ai-wx.blog.csdn.net_article_details_115610626]  
> 未经授权，禁止转载！恶意转载，后果自负！尊重原创，远离剽窃！

--------------------

### 2.4 最小路径和 ###

#### 题目 ####

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    说明：每次只能向下或者向右移动一步。

**示例 ：**  
![在这里插入图片描述][20210412225734858.png]  
输入：grid = \[\[1,3,1\],\[1,5,1\],\[4,2,1\]\]  
输出：7  
解释：因为路径 1→3→1→1→1 的总和最小。

提示：  
m = grid.length  
n = grid\[i\].length  
1 <= m, n <= 200  
0 <= grid\[i\]\[j\] <= 100

#### 解析 ####

分析题目可知：每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，所以可以使用动态规划求解磁体。

**假设 dp\[i\]\[j\] 表示从左上角出发到(i, j)位置的最小路径和，其中 0<=i<=n-1，0<=j<=m-1。**

首先确定初始条件：**dp\[0\]\[0\] = grid\[0\]\[0\]**

对于dp 中的其余元素，通过以下**状态转移方程**计算：

*  当 i>0 且 j=0 时，**dp\[i\]\[0\] = dp\[i-1\]\[0\]+grid\[i\]\[0\]** (第一列的元素只能由它正上方的元素移动而来)
 *  当 i=0 且 j>0 时，**dp\[0\]\[j\] = dp\[0\]\[j-1\]+grid\[0\]\[j\]** (第一行的元素只能由它的左边移动而来)
 *  当 i>0 且 j>0 时，**dp\[i\]\[j\] = min(dp\[i-1\]\[j\]，dp\[i\]\[j-1\]) + grid\[i\]\[j\]** (对于其他任意元素)

最后得到 dp\[m-1\]\[n-1\] 的值即为从网格左上角到网格右下角的最小路径和。

C++代码实现如下：

class Solution { 
    public:
        int minPathSum(vector<vector<int>>& grid) { 
    
            if(!grid.size()||!grid[0].size()) return 0;
            int m = grid.size();
            int n = grid[0].size();
    
            auto dp = vector < vector <int> > (m, vector <int> (n));
            dp[0][0] = grid[0][0];
    
            for(int i=1; i<m; ++i)
                dp[i][0] = dp[i-1][0] + grid[i][0];
            for(int j=1; j<n; ++j)
                dp[0][j] = dp[0][j-1] + grid[0][j];
                
            for(int i=1; i<m; ++i)
                for(int j=1; j<n; ++j)
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            return dp[m-1][n-1];
        }
    };

代码提交结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]  
复杂度分析：

*  时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。
 *  空间复杂度：O(mn)，二维数组dp\[m\]\[n\]占用额外的空间内存。

--------------------

### 2.5 按摩师 ###

#### 题目 ####

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
    在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
    给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
    
    示例 1：
    输入： [1,2,3,1]
    输出： 4
    解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
    
    示例 2：
    输入： [2,7,9,3,1]
    输出： 12
    解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
    
    示例 3：
    输入： [2,1,4,5,3,1,1,3]
    输出： 12
    解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/the-masseuse-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 题解 ####

**方法：**

此题与常规的动态规划题稍有不同，因为题目条件不多，所以很难找到递推关系！题目唯一的条件是：**每个预约都可以选择接或不接，且不可接相邻的预约，** 这也就成了本题的关键信息。

由于第i个预约可接可不接，所以对于第i个预约有两种状态。因此，可以设定 **dp0\[i\] 表示第 i 次没有预约时的最长总预约时间，dp1\[i\] 表示第 i 次被预约时的最长总预约时间**。

根据题目条件，容易推出初始条件：**dp0\[0\] = 0， dp1\[0\] = nums\[0\]**。

递推公式如下：

*  第 i 次没有预约时的最长总预约时间：**dp0\[i\] = max(dp0\[i-1\], dp1\[i-1\])**
 *  第 i 次被预约时的最长总预约时间：**dp1\[i\] = dp0\[i-1\] + nums\[i-1\]**

最终，所得的最长总预约时间为：**max(dp0\[n-1\], dp1\[n-1\])** , 其中 n=nums.size()

实现如下：

class Solution { 
    public:
        int massage(vector<int>& nums) { 
            int n = nums.size();
            if(n==0)
                return 0;
            vector<int> dp0(n); // 表示第i次没有预约的最长时间
            vector<int> dp1(n); // 表示第i次被预约的最长时间
    
            dp0[0] = 0;
            dp1[0] = nums[0];
    
            for(int i=1; i<n; ++i)
            { 
                dp0[i] = max(dp0[i-1], dp1[i-1]);
                dp1[i] = dp0[i-1]+nums[i];
            }
            return max(dp0[n-1], dp1[n-1]);
        }
    };

###  本文将持续更新，欢迎大家点赞收藏！ ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/952bce9b4e1c4f8f84183ff48b01a5f1.png
[d8351ed24c637db3fef0eef05348f356.png]: /images/20221022/ff8c2b736210496184b129b168f03710.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221022/fef3cbf7bac24e22bee808c069b02cf7.png
[https_blog.csdn.net_wjinjie]: https://blog.csdn.net/wjinjie
[https_ai-wx.blog.csdn.net_article_details_115610626]: https://ai-wx.blog.csdn.net/article/details/115610626
[20210412225734858.png]: /images/20221022/9a1924ecbe09408aacb97faeefaef1a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221022/b1469ce1caeb48edbf9db7e031080085.png