C++ 吃透动态规划算法

电玩女神 2022-09-04 14:43 180阅读 0赞

本文需要花费半天乃至一天的时间来学习, 前提内功深厚, 不然一时半会还真看不懂  
觉得有用给个三连呗 !!!

### 文章目录 ###

*  1. 介绍
 *  2. 子序列问题
 *   *  1143.最长公共子序列
     *  300.最长递增子序列
     *  2.1 最长递增子序列应用
     *   *  354.俄罗斯套娃
         *  \[17.08 马戏团人塔\](https://leetcode-cn.com/problems/circus-tower-lcci/)
 *  3. 路径问题
 *   *  120.三角形最小路径和
     *  \[64. 最短路径和\](https://leetcode-cn.com/problems/minimum-path-sum/)
     *  \[221. 最大正方形\](https://leetcode-cn.com/problems/maximal-square/)
 *  4. 背包问题
 *   *  01背包问题
     *  01背包问题的应用 是否可以一个数组分成和相等的两部分
     *  4.2 完全背包问题
     *  \[416. 是否可以一个数组分成和相等的两部分\](https://leetcode-cn.com/problems/partition-equal-subset-sum/)
 *  5. 分割问题
 *   *  \[410. 分割数组的最大值\](https://leetcode-cn.com/problems/split-array-largest-sum/)
     *  \[279. 完全平方数\](https://leetcode-cn.com/problems/perfect-squares/)
 *  6. 递进问题(类似斐波那契数列)
 *   *  \[322. 零钱兑换\](https://leetcode-cn.com/problems/coin-change/)
     *  \[53. 最大子序和\](https://leetcode-cn.com/problems/maximum-subarray/)
     *  \[413. 等差数列划分\](https://leetcode-cn.com/problems/arithmetic-slices/)
     *  华为笔试题: 外卖员到达目标楼层的最短消费时间
 *  7. 两次dp 夹击解题
 *   *  \[542. 每个位置到0的距离\](https://leetcode-cn.com/problems/01-matrix/)
     *  \[42. 接雨水\](https://leetcode-cn.com/problems/trapping-rain-water/)

# 1. 介绍 #

*  动态规划 (Dynamic Programming, DP)
 *  保存子问题, 避免重复计算
 *  关键是: 找到转移方程, 确定边界条件, 明确dp数组含义
 *  比如我们熟悉的斐波那契数列, 其实dp跟递归是一样的, 只是因为递归占用时间和空间较大, 所以尽可能使用dp解题, 事半功倍.

int feiB(int n){ 
    	if(n<=1) return n;
    	vector<int>dp(n+1, 0); //多出来一个, 因为feiB(3) = 2
    	dp[0]=0, dp[1]=1;  // 边界条件
    	for(int i=2; i<=n; i++){  
    		dp[i] = dp[i-1]+dp[i-2]; // 转移方程
    	}
    	cout<<n<<"的结果是"<<dp[n]<<endl;
    	return dp[n];
    }

# 2. 子序列问题 #

解题思路:

1.  思考问题能不能转化成树的形式
2.  思考树是不是自底向上求取结果
3.  根据这个树, 确定自底向上的关系式, 比如上层节点A = 下层节点(A1+A2)
4.  具体操作见下面的示例图解

这部分问题, 笔试面试的时候出的特别多, 因为这部分问题如果有思路, 很快就能确定解决方案, 并且代码量不多, 只需要理解动态规划就会很好写, 具体的题目见下面, 对于前两个题两个题太重要了, 一定要牢牢掌握住, 为后面的笔试面试奠基牢固的基础, 因为第三个题往后都是这两个题的延伸延伸延伸.

## [1143.最长公共子序列][1143.] ##

> 给定两个字符串 `text1` 和 `text2`，返回这两个字符串的最长 **公共子序列** 的长度。如果不存在 **公共子序列** ，返回 `0` 。

输入：text1 = "abcde", text2 = "ace" 
    输出：3  
    解释：最长公共子序列是 "ace" ，它的长度为 3 。
    输入：text1 = "abc", text2 = "abc"
    输出：3
    解释：最长公共子序列是 "abc" ，它的长度为 3 。
    输入：text1 = "abc", text2 = "def"
    输出：0
    解释：两个字符串没有公共子序列，返回 0 。

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]

class Solution { 
    public:
        int longestCommonSubsequence(string s1, string s2) { 
            int m=s1.size(), n=s2.size();
            vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 默认dp[i][j](0,0) = 0
            for(int i=1; i<=m; i++){ 
                for(int j=1; j<=n; j++){ 
                    if(s1[i-1] == s2[j-1]){  // 字符串索引从0开始, dp[1][1]表示s1[0]和s2[0]公共子序列
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }else{ 
                        dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                    }
                }
            }
            return dp[m][n];
        }
    };

## [300.最长递增子序列][300.] ##

> 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。  
> 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    输入：nums = [0,1,0,3,2,3]
    输出：4

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]  
由上图可知, 比如第4个位置对应的最长递增子序列, 其结果跟前三个位置都相关

class Solution { 
    public:
        // 可能是动态规划, 从底层往上层走, 发现4跟123有关, 即4是123其中最大值加一如果4大于123
        int lengthOfLIS(vector<int>& nums) { 
            if(nums.empty()) return 0;
            int n=nums.size();
            
            vector<int> dp(n, 1); // 只要数组不空, 递增子序列最差也是1
            for(int i=0; i<n; i++){ 
                for(int j=0; j<i; j++){ 
                    if(nums[i] > nums[j]){ 
                        dp[i] = max(dp[i], dp[j]+1);
                    }
                }
            }
            // print_v(dp);
            return *max_element(dp.begin(), dp.end());
        }
    };

## 2.1 最长递增子序列应用 ##

### [354.俄罗斯套娃][354.] ###

### [17.08 马戏团人塔][17.08] ###

做完上面那俩题之后, 在做这个题, 如果这个题还不会做, 请重复做上面那俩题, 直到不看答案, 能够解决这个题, **算成功**

> 给你一个二维整数数组 envelopes ，其中 envelopes\[i\] = \[wi, hi\] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。  
> 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。  
> 注意：不允许旋转信封。

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
    输出：3
    解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
    
    输入：envelopes = [[1,1],[1,1],[1,1]]
    输出：1

思考:  
首先想一下, 如果说把这个二维变成一维, 是不是就是最长递增子序列  
只不过这个题增加了一个维度, 那我们思考一下, 能不能先对一侧进行排序, 然后在另一侧计算最长递增子序列呢???  
答案很显然是可以的

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
    先对list的第一列排序, [[2,3], [5,4], [6,4], [6,7]]
    然后在对第一列相等的, 倒叙排序第二列 , [[2,3], [5,4], [6,7], [6,4]]
    然后在看[3,4,7,4]的最长递增子序列即可
    思考: 第一个排序可以理解, 为何倒叙排列第二列???
    参考 [[2,3], [5,4], [5,8], [6,7], [6,6], [6,3]]
    这里如果[[5,4], [5,8]]是顺序, 则[3,4,8,7] 最长子序列是3, 也就是吧[5,4] 包金来了, 
    但是[[6,7], [6,6], [6,3]], [3,4,8,7,6,3], 就不会把[[6,6], [6,3]]包进来;

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]

class Solution { 
    public:
        struct myCompare{ 
            bool operator()(vector<int> &a, vector<int> &b){ 
                // 先对第一列进行排序, 如果第一列有相等的比如[2,1], [2,3] 在对第二列进行排列成[2,3],[2,1],
                return (a[0] < b[0]) || (a[0]==b[0] && a[1] > b[1]);
            }
        };
    
        int maxEnvelopes(vector<vector<int>> &nums){ 
            if(nums.empty()) return 0;
            int n=nums.size();
            sort(nums.begin(), nums.end(), myCompare()); // 按要求排序
            vector<int>dp (n, 1);
            for(int i=0; i<n; i++){ 
                for(int j=0; j<i; j++){ 
                    if(nums[i][1] > nums[j][1]){ 
                        dp[i] = max(dp[i], dp[j]+1);
                    }
                }
            }
            return *max_element(dp.begin(), dp.end());
            
        }
    };

# 3. 路径问题 #

## [120.三角形最小路径和][120.] ##

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出：11
    解释：如下面简图所示：
       2
      3 4
     6 5 7
    4 1 8 3
    自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]

class Solution { 
    public:
        int minimumTotal(vector<vector<int>>& nums) { 
            if(nums.empty() || nums[0].empty()) return 0;
    
            int m=nums.size(), n=nums[m-1].size();
            // dp[i][j] 表示从[i,j] 到低的最小路径和
            vector<vector<int>> dp(m, vector<int>(n)); 
    
            // 自底向上计算最小值
            for(int i=0; i<n; i++){ 
                dp[m-1][i] = nums[m-1][i];
            }
    
            for(int i=m-2; i>=0; i--){  // 从倒数第二行往上
                for(int j=0; j<=i; j++){  // 从左往右
                    dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + nums[i][j];
                }
            }
            return dp[0][0];
        }
    };

## [64. 最短路径和][64.] ##

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

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出：7
    解释：因为路径 1→3→1→1→1 的总和最小。
    输入：grid = [[1,2,3],[4,5,6]]
    输出：12

![在这里插入图片描述][b159186765ce499ab6a6bc0d88062488.png]

**思考:**

1.  最短路径和有点像贪婪算法的意思
2.  从左上角开始, 找右/下最小值走, 但是显然不对, 就如上图所示
3.  但是可以想一下, 当前值只跟左/上两个有关系, 所以最终`dp[i][j]`就可表示为从`(0,0)->(i,j)`的对小花费

dp[i][j] = min(dp(i-1, j) , dp(i, j-1)) + nums[i][j];
    边界条件就是dp的第一列和第一行是nums的累加

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

## [221. 最大正方形][221.] ##

> 在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    输出：4

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]

1.  `dp[i][j]`表示从`i,j`到左上的正方形边长

class Solution { 
    public:
        int min_3(int &a, int &b, int &c){ 
            return min(min(a, b),c);
        }
    
        /* 1. dp[i][j] 表示从(i,j)到 左上方 最大的正方形的边长 2. dp[i][j] = min(左, 上, 左对角) + 1 */
        int maximalSquare(vector<vector<char>>& nums) { 
            if(nums.empty() || nums[0].empty()) return 0;
            int m=nums.size(), n=nums[0].size();
    
            int ans=0;
            vector<vector<int>>dp(m, vector<int>(n,0));
            for(int i=0; i<m; i++){ 
                for(int j=0; j<n; j++){ 
                    if(i==0 || j==0){ 
                        dp[i][j] = nums[i][j] - '0';
                    }
                    else if(nums[i][j] == '1'){ 
                        dp[i][j] = min_3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                    }
                    ans = max(ans, dp[i][j]);
                }
            }
            return ans*ans;
        }
    };

# 4. 背包问题 #

*  组合优化的 NP 完全问题
 *  有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。
 *  对于背包问题动态方程,
 *  设dp\[i,j\]表示第i物品容量为j的位置背包的价值最多  
    因此可以考虑这样求解  
    i物品放入背包, 此时背包减去i物品重量后,剩余空间是j-w\[i\], 所以找到上一个物品的j-w\[i\]

## 01背包问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 5]

*  这里需要注意的是: 边界条件
 *  跳转关系见图示  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 6]

/* 1. dp含义: dp[i][j] 表示任取0-i的物品放到容量为j的背包里面的最大值 2. 递推公式: dp[i][j]取决于当前物品 i不放 dp[i][j]=dp[i-1][j] 就跟上一个物品放不放一致 i放dp[i][j]=dp[i-1][j-weight[i]] + value[i] 空间减掉当前物品空间, 价值加上当前拿物品的价值, 3. 初始化: 第一行和第一列 4. 循环顺序: */
    int bakage_01(vector<int> weight, vector<int> value, int maxW){ 
        vector<vector<int>> dp(weight.size(), vector<int>(maxW+1, 0));
        for(int i=0; i<weight.size(); i++){  //物品
            for(int j=1; j<=maxW; j++){  // 背包容积
                if(i == 0 && weight[0] <= j) {  // 第一行, 第一个物品如果重量大于背包容量, 则为value0
                    dp[0][j] = value[0];
                }else if(j < weight[i]){  // 背包容积小
                    dp[i][j] = dp[i-1][j]; //只跟上一个物品相关
                }else{ 
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }
        print_vv(dp);
        return dp[weight.size()-1][maxW];
    }

*  空间压缩  
    因为上面dp\[i\]行值只与i-1相关, 所以只需要定义一维空间, 一行一行进行填写, 最后完成dp\[j\]即为所求

// 空间压缩
    int knapsack_optimize(vector<int> weights, vector<int> values, int N, int W) { 
    	vector<int>dp(W+1, 0);
    	int w,v;
    	for(int i=1; i<=N; i++){ 
    		w=weights[i-1], v=values[i-1];
    		for(int j = W; j>=w; j--){  // 这里大于w是为了去除没用的, 也可以为j>0
    			dp[j] = max(dp[j], dp[j-w]+v);
    		}
    		print_v(dp);
    	}
    	return dp[W];
    }

## 01背包问题的应用 是否可以一个数组分成和相等的两部分 ##

[416. 是否可以一个数组分成和相等的两部分][416.]

> 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入：nums = [1,5,11,5]
    输出：true
    解释：数组可以分割成 [1, 5, 5] 和 [11] 。
    输入：nums = [1,2,3,5]
    输出：false
    解释：数组不能分割成两个元素和相等的子集。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 7]

class Solution { 
    public:
        bool canPartition(vector<int>& nums) { 
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if(sum & 1) return false; 
            int target = sum/2;
            if(*max_element(nums.begin(), nums.end()) > target) return false;
    
            vector<vector<bool>> dp(nums.size(), vector<bool>(target+1, false));
            dp[0][nums[0]] = true; // 第一行的第nums[0]列为true 初始化, 因为一个物品放到背包中正好等于背包容积
            for(int i=1; i<nums.size(); i++){ 
                for(int j=1; j<=target; j++){ 
                    if(nums[i] > j) dp[i][j] = dp[i-1][j]; // 当前物体容积太大, 不取, 则跟上面的一样
                    else if(nums[i] == j) dp[i][j] = true; // 当前值正好等于背包容积
                    else{ 
                        // 当前值小于背包容积, 放进去的话是dp[i-1][j-nums[i]], 不放进去的话是dp[i-1][j]
                        dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j]; 
                    }
                }
            }
            return dp[nums.size()-1][target];
        }
    };

## 4.2 完全背包问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 8]

int knapsack_fully(vector<int> weights, vector<int> values, int N, int W) { 
    	std::vector<std::vector<int>> dp(N+1, std::vector<int>(W+1, 0));
    	int w,v;
    	for(int i=1; i<=N; i++){ 
    		w=weights[i-1], v=values[i-1];
    		for(int j = 1; j<=W; j++){ 
    			if(j>=w){   
    				dp[i][j] = max(dp[i-1][j], v+dp[i][j-w]);
    			}else{ 
    				dp[i][j] = dp[i-1][j];
    			}
    		}
    	}
    	print_vv(dp);
    	return dp[N][W];
    }

## [416. 是否可以一个数组分成和相等的两部分][416.] ##

*  Input: \[1,5,11,5\]
 *  Output: true
 *  仔细一看, 本题不就是一道01背包问题么
 *  将所有值相加对半, 等于11
 *  也就是背包最大值为11, input是物品的重量, 价值不用考虑  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 7]

/** * @Author zjq * @DateTime 2021-02-08 * @技巧 与01背包问题相似, 都是小问题到大问题, 比如先判断前i个数, 是否能和为nums/2 * @function * @param nums 数列 * @return 是否能分成两个数列, 使得两数列之和相等 */
    bool canPartition(vector<int> nums) { 
    	int sum = accumulate(nums.begin(), nums.end(), 0);
    	if (sum % 2) return false;
    	int target = sum / 2, n = nums.size();
    	vector<vector<bool>> dp(n+1, vector<bool>(target + 1, false));
    	for (int i = 0; i <= n; ++i) { 
    		dp[i][0] = true;
    	}
    	print_vv(dp);
    	for (int i = 1; i <= n; ++i) { 
    		for (int j = nums[i-1]; j <= target; ++j) { 
    			dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
    		}
    		print_vv(dp);
    	}
    	return dp[n][target];
    }
    
    bool canPartition_optimize(vector<int> nums) { 
    	int sum = accumulate(nums.begin(), nums.end(), 0);
    	if (sum % 2) return false;
    	int target = sum / 2;
    	vector<vector<bool>> dp(nums.size(), vector<bool>(target + 1, false));
    	dp[0][nums[0]] = true; //设置第一边界条件
    	for (int i = 1; i < nums.size(); ++i) { 
    		for (int j = 0; j <= target; ++j) { 
    			if(nums[i] == j) {    //选择当前值, 正好等于 直接设置为1
    				dp[i][j]==true;
    			}else if(nums[i]<j){  // 选择当前值, 小于
    				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
    			}else{ 
    				dp[i][j] = dp[i-1][j]; // 首先默认不加入当前值nums[i]
    			}
    		}
    		if(dp[i][target]) return true; // 没行结束判定一下最后一个值, target已经实现, 就不用在继续循环了
    	}
    	print_vv(dp);
    	return dp[nums.size()-1][target];
    }
    
    bool canPartition_optimize2(vector<int> nums) { 
    	int sum = accumulate(nums.begin(), nums.end(), 0);
    	if (sum % 2) return false;
    	int target = sum / 2;
    	vector<vector<bool>> dp(nums.size(), vector<bool>(target + 1, false));
    	dp[0][0] = true; // 边界条件
    	dp[0][nums[0]] = true; //设置第一边界条件
    	for (int i = 1; i < nums.size(); ++i) { 
    		for (int j = 0; j <= target; ++j) { 
    			dp[i][j] = dp[i-1][j]; // 首先默认不加入当前值nums[i]
    			if(nums[i]<=j){  // 选择当前值, 小于
    				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
    			}
    		}
    		// if(dp[i][target]) return true;
    	}
    	print_vv(dp);
    	return dp[nums.size()-1][target];
    }
    
    vector<int> list={ 1,5,11,5};
    canPartition(list);
    // canPartition_optimize2(list);

# 5. 分割问题 #

## [410. 分割数组的最大值][410.] ##

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
    设计一个算法使得这 m 个子数组各自和的最大值最小。
    输入：nums = [7,2,5,10,8], m = 2
    输出：18
    解释：
    一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
    因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 9]

class Solution { 
    public:
        int splitArray(vector<int>& nums, int m) { 
            int n = nums.size();
            vector<vector<long long>> f(n + 1, vector<long long>(m + 1, LLONG_MAX));
            vector<long long> sub(n + 1, 0);
            for (int i = 0; i < n; i++) { 
                sub[i + 1] = sub[i] + nums[i];
            }
            f[0][0] = 0;
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= min(i, m); j++) { 
                    for (int k = 0; k < i; k++) { 
                        f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]));
                    }
                }
            }
            return (int)f[n][m];
        }
    };

## [279. 完全平方数][279.] ##

> 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。  
> 输入：n = 12  
> 输出：3  
> 解释：12 = 4 + 4 + 4

class Solution { 
    public:
        int numSquares(int n) { 
            if(n < 1) return 0;
            vector<int> dp(n+1, n);
            dp[0] = 0, dp[1] = 1;
            for(int i=1; i<=n; i++){ 
                for(int j=1; j*j<=i; j++){ 
                    dp[i] = min(dp[i], dp[i-j*j]+1);
                }
            }
            return dp[n];
        }
    };

# 6. 递进问题(类似斐波那契数列) #

解题思路:

1.  先根据问题画树形图
2.  由树形图推出前后关系
3.  在确定初始dp

## [322. 零钱兑换][322.] ##

> 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。  
> 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

输入：coins = [1, 2, 5], amount = 11
    输出：3 
    解释：11 = 5 + 5 + 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 10]

class Solution { 
    public:
    int coinChange(vector<int>& nums, int target) { 
        if(target==0)  return 0;
        if(nums.empty() || *min_element(nums.begin(), nums.end()) > target) return -1;
        vector<int> dp(target+1, target+1); // 默认都是最大
        sort(nums.begin(), nums.end());
    
        for(int &a : nums){ 
            if(a > target) nums.pop_back();
        }
        int n = nums.size();
        // print_v(nums);
        // 先把每个需要一个硬币就搞定的安排上
        for(int &a: nums) dp[a] = 1; 
    
        // 把前面的都给赋值为0
        for(int i=0; i<nums[0]; i++) dp[i] = 0;
        
        // 从第一个硬币下一个位置开始
        for(int i=nums[0]+1; i<=target; i++){ 
            for(int j=0; j<n; j++){ 
                // 当前位置减去一个硬币还有空闲, 并且这个空闲有硬币可以弥补
                int a = i-nums[j];
                if((a >= 0) && (dp[a] != target+1) &&  (dp[a] != 0)) { 
                    dp[i] = min(dp[a]+1, dp[i]);
                }
            }
        }
        return dp[target]==target+1 ? -1 : dp[target];
    }
    };

## [53. 最大子序和][53.] ##

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            if(nums.empty()) return 0;
    
            int n=nums.size();
            vector<int> dp(n);
            dp[0] = nums[0];
    
            for(int i=1; i<n; i++){ 
                dp[i] = max(dp[i-1]+nums[i], nums[i]);
            }
            return *max_element(dp.begin(), dp.end());
        }
    };

## [413. 等差数列划分][413.] ##

/* 输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。 */
    
    class Solution { 
    public:
        /* 等差数列的要求是nums[i]-nums[i-1] == nums[i-1]-nums[i-2] 因此当前值跟前两个值有关系, 因此与斐波那契一样, 只需要定义前两个值即可 */
        int numberOfArithmeticSlices(vector<int>& nums) { 
            if(nums.empty()) return 0;
            int n=nums.size();
            vector<int> dp(n, 0); // dp[i] 表示从0-i总共多少个等差数列
            for(int i=2; i<n; i++){ 
                if(nums[i]-nums[i-1] == nums[i-1]-nums[i-2]){ 
                    dp[i] = dp[i-1] + 1;
                }
            }
            return accumulate(dp.begin(), dp.end(), 0);
        }
    };

## 华为笔试题: 外卖员到达目标楼层的最短消费时间 ##

/* 题目: 外卖员小w, 每天在大厦运送外卖, 大厦共L层, 当小W处于第N层, 每分钟通过步行上楼到达N+1, 或下楼到达N-1, 或者电梯到达2N 给定小w所处位置N, 目的楼层M, 计算小w送达的最短时间 分析: 首先选择动态规划解题, dp[i] 表示从小王位置到达i点的时间 小王能走得路子只有 +1, -1, *2 因此 当目标值在楼下, 只能-1 当目标值在楼上分两种情况考虑: +1往上, 或者楼下*2, 两者的最小值 */
    int stairs(int location, int target){ 
        // 如果当前位置在目前位置以下, 只能向下走
        if(target<=location) return location-target; 
    
        vector<int> dp(target+1, 0);
    
        // 当目的地在小王脚下时, 直接赋值
        for(int i=1; i<location; i++){ 
            dp[i] = location-i;
        }
    
        // 当目的地在小王头上时, 分类讨论
        for(int i=location+1; i<=target; i++){ 
            int down = 1+dp[i-1]; // 向上走一步的长度
            // 比如小王9楼, 当前所求是10楼, 可以是5楼*2
            // 比如当前所求是11楼, 则可以是5楼*2+1, 也就是后面的+2
            int el = i%2==0 ? dp[i/2]+1 : 2+dp[(i+1)/2]; 
            dp[i] = min(down, el); // 是直接上走得, 还是从下面*2上走的
        }
        return dp[target];
    }

# 7. 两次dp 夹击解题 #

## [542. 每个位置到0的距离][542. _0] ##

> 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。  
> 两个相邻元素间的距离为 1 。

解题思路:

1.  首先设置二维数组, dp\[i\]\[j\] 表示位置i,j与0最近的距离
2.  默认dp填充最大值(这里可以设置成二维矩阵的对交线长度)
3.  因为需要一步步查找当前位置与0的距离
4.  所以从上往下, 从左往右开始, 当遇到0时, 直接置零, 当遇到1时, 直接上和左的值加一与当前值进行比大小
5.  然后从下往上, 从右往左, 与上面同理

# nums
    1 0 1 0 0 
    1 0 1 0 1 
    0 1 0 0 0 
    0 0 1 1 1 
    1 0 1 0 0 
    # 从上往下, 从左往右
    10000 0 1 0 0 
    10000 0 1 0 1 
    0 1 0 0 0 
    0 0 1 1 1 
    1 0 1 0 0 
    # 从下往上, 从右往左
    1 0 1 0 0 
    1 0 1 0 1 
    0 1 0 0 0 
    0 0 1 1 1 
    1 0 1 0 0

class Solution { 
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& nums) { 
            if(nums.empty() || nums[0].empty()) return { };
            int m=nums.size(), n=nums[0].size();
            vector<vector<int>> dp(m, vector<int>(n, 10000)); // 因为n<=10^4
            // 先从左往右, 从上往下, 这样就可以确定一半位置
            for(int i=0; i<m; i++){ 
                for(int j=0; j<n; j++){ 
                    if(nums[i][j] == 0) dp[i][j] = 0;
                    else{ 
                        if(i > 0) dp[i][j] = min(dp[i][j], dp[i-1][j]+1); // 上→下
                        if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j-1]+1); // 左→右
                    }
                }
            }
    
            for(int i=m-1; i>=0; i--){ 
                for(int j=n-1; j>=0; j--){ 
                    if(nums[i][j] == 0) { }
                    else{ 
                        if(i < m-1) dp[i][j] = min(dp[i][j], dp[i+1][j]+1); // 上→下
                        if(j < n-1) dp[i][j] = min(dp[i][j], dp[i][j+1]+1); // 左→右
                    }
                }
            }
            return dp;
        }
    };

## [42. 接雨水][42.] ##

> 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。  
> 输入：height = \[0,1,0,2,1,0,1,3,2,1,2,1\]  
> 输出：6  
> 解释：上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。  
> ![在这里插入图片描述][c48babccc5ff44d8b337f6b562891715.png]

**解题思路:**

*  从左向右遍历得到左侧最大值
 *  从右向左遍历得到右侧最大值
 *  两个最大值减去当前值就是积水  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95a2Q5peg5oKUIQ_size_20_color_FFFFFF_t_70_g_se_x_16]

int trap(vector<int> &height){ 
        int ans = 0;
        int n = height.size();
        if(n<3) return 0; // 低于三个柱子不可能积水
    
        // 从左往右遍历得到左侧最大值
        vector<int> left_max_arr(n); 
        left_max_arr[0] = height[0];
        for(int i=1; i<n; i++){ 
            left_max_arr[i] = max(left_max_arr[i-1], height[i]);
        }
    
        // 从右往左遍历得到右侧最大值
        vector<int> right_max_arr(n); 
        right_max_arr[n-1] = height[n-1];
        for(int i=n-2; i>=0; i--){ 
            right_max_arr[i] = max(right_max_arr[i+1], height[i]);
        }
    
        // 合并求解
        for(int i=0; i<n; i++){ 
            ans += min(left_max_arr[i], right_max_arr[i]) - height[i];
        }
        return ans;
    }

[1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]: /images/20220829/c4008bdae8314e6087c0dd1e7eed082c.png
[300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]: /images/20220829/0b5d1601877a497abf389b995f51b45f.png
[354.]: https://leetcode-cn.com/problems/russian-doll-envelopes/
[17.08]: https://leetcode-cn.com/problems/circus-tower-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]: /images/20220829/09638afebbf34d548765f29692e38557.png
[120.]: https://leetcode-cn.com/problems/triangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]: /images/20220829/3bfb37392c7142ccbc929908f9198c1b.png
[64.]: https://leetcode-cn.com/problems/minimum-path-sum/
[b159186765ce499ab6a6bc0d88062488.png]: /images/20220829/f433bedb421c45628e609cfa4d88701a.png
[221.]: https://leetcode-cn.com/problems/maximal-square/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]: /images/20220829/118157f9eeba489c81aa2193ae2a0d10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 5]: /images/20220829/3f64e71ac0a34b7ca455971c61fbc060.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 6]: /images/20220829/da6ff7240f8e4e9e80b6a12d959dbf40.png
[416.]: https://leetcode-cn.com/problems/partition-equal-subset-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 7]: /images/20220829/9f4fbd555a754b318dbcb4c1b8c9310f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 8]: /images/20220829/c85d207c7cf3442b81702f6cb86a1a02.png
[410.]: https://leetcode-cn.com/problems/split-array-largest-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 9]: /images/20220829/00e5787e2c0a4354b5f526552ed4564b.png
[279.]: https://leetcode-cn.com/problems/perfect-squares/
[322.]: https://leetcode-cn.com/problems/coin-change/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 10]: /images/20220829/0a6ad02a85654f1f82581c49199338e3.png
[53.]: https://leetcode-cn.com/problems/maximum-subarray/
[413.]: https://leetcode-cn.com/problems/arithmetic-slices/
[542. _0]: https://leetcode-cn.com/problems/01-matrix/
[42.]: https://leetcode-cn.com/problems/trapping-rain-water/
[c48babccc5ff44d8b337f6b562891715.png]: /images/20220829/4cadb71f7c944ac9ba849ac530cd894e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95a2Q5peg5oKUIQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/5fa5b9e578cd447ca149178f8c8010cf.png