devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ，三道题目深度解析

作者：IT小白 | 2024-04-05 13:40:08

赞

踩

【二十】【动态规划】879. 盈利计划、377. 组合总和 Ⅳ、96. 不同的二叉搜索树 ，三道题目深度解析

动态规划

动态规划就像是解决问题的一种策略，它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题，并将每个小问题的解保存起来。这样，当我们需要解决原始问题的时候，我们就可以直接利用已经计算好的小问题的解，而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法：

  1. 基础步骤（base case）：首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况，可以直接验证命题是否成立。

  2. 归纳步骤（inductive step）：假设命题在某个情况下成立，然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤，我们可以推导出命题在所有情况下成立的结论。

动态规划：

  1. 状态表示：

  2. 状态转移方程：

  3. 初始化：

  4. 填表顺序：

  5. 返回值：

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中，首先得到状态在最小的基础情况下的值，然后通过状态转移方程，得到下一个状态的值，反复迭代，最终得到我们期望的状态下的值。

接下来我们通过三道例题，深入理解动态规划思想，以及实现动态规划的具体步骤。

879. 盈利计划 - 力扣（LeetCode）

题目解析

状态表示

这个问题本质上是，

  1. 挑选出一些工作作为一个集合，这个集合满足某些要求，解决某些问题。而背包问题就是挑选出一些物品作为一个集合，这个集合满足某些要求，解决某些问题。

  2. 挑选出来的工作不可以无限选取，所以属于二维01背包问题。

背包问题的状态表示是，

定义dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中，所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选，总体积恰好为j，所有选法中，所能达到的最大价值。

我们根据背包问题的状态表示，定义出该问题的状态表示。

因此我们可以定义，dp[i][j][k]表示，从前i个工作中挑选，总需人数不超过j，总利润不少于k，总盈利计划个数。

状态转移方程

状态转移方程通常都是根据最后一个位置的具体状况进行分类讨论。

  1. 如果不选择第i个工作， 此时只能从前i-1个工作中挑选出集合，此时dp[i][j][k]=dp[i-1][j][k]。

  2. 如果选择第i个工作， 此时第i个工作需要的人数为group[i-1]，产生的利润为profit[i-1]，本来总人数不能超过j，选取第i个工作后，总人数不能超过j-group[i-1]，本来总利润需要不少于k，选取第i个工作后，总利润需要不少于k-profit[i-1]，因此dp[i][j][k]=dp[i-1][j-group[i-1]][k-profit[i-1]]。表示在前i-1个工作中挑选集合的集合个数，每一个集合都加入第i个工作，此时的集合个数为dp[i][j][k]。此时还需要判断j-guoup[i-1],k-profit[i-1]是否小于0，的情况。小于0就越界了。

    1. 如果j-group[i-1]<0, 表示第i个工作需要的人数就大于了j，此时dp[i][j][k]=0。

    2. 如果j-group[i-1]>=0, 说明此时可以完成第i个工作，dp[i][j][k]=dp[i-1][j-group[i-1][k-profit[i-1]]，还需要考虑k-profit[i-1]的正负性。

      1. 如果k-profit[i-1]<0, 表示第i个工作产生的利润就可以满足最低需求利润，所以再从前面工作中挑选，不需要考虑它的利润条件，即产生的利润大于等于0即可。此时dp[i][j][k]=dp[i-1][j-group[i-1]][0]。

      2. 如果k-profit[i-1]>=0, 此时dp[i][j][k]=dp[i-1][j-group[i-1]][k-profit[i-1]]。

综上所述，将上述情况进行合并和简化，得到状态转移方程为，

 

  1.         dp[i][j][k] = dp[i - 1][j][k];
  2.         if (j - group[i - 1] >= 0)
  3.             dp[i][j][k] = (dp[i][j][k]+dp[i - 1][j - group[i - 1]]
  4.                              [max(0, k - profit[i - 1])])%MOD;
 

MOD=1e9+7，因为题目说得到的数可能很大，需要对MOD取余，所以两个数每相加，就对MOD取余。
 

初始化
 

根据状态转移方程，我们知道，推导（i，j，k）位置的状态需要用到（i-1，j，k）位置的状态，if判断保证j-group[i-1]一定不会小于0，dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]，所以这个状态中只需要考虑（i-1）。所以我们需要初始化第一行，推导第一行的时候会发生越界的情况，此时没有前驱状态。
 

i==0，表示不选工作，人数不超过j，集合利润不少于k，集合个数，此时只有dp[0][j][0]=1,其他都为0。
 

故初始化为，
 

 

  1.         for (int j = 0; j <= n; j++) {
  2.             dp[0][j][0] = 1;
  3.         }
 

填表顺序
 

根据状态转移方程，我们在推导（i，j，k）位置的状态时，需要用到（i-1，j，k）（i-1，j-group[i-1],k-profit[i-1]）位置的状态。这些状态不会越界，初始化保证了他们不会越界。
 

  1.  
    固定i， i需要从小到大变化，当推导（i，j，k）位置状态时，（i-1，，）位置状态已经得到，所以j，k的变化可以从小到大，也可以从大到小。
     
  2.  
    固定j， j的变化需要从小到大，又因为需要用到（i-1，j，k）位置的状态，所以i的变化需要从小到大，此时k的变化可以从小到大也可以从大到小。
     
  3.  
    固定k， k的变化需要从小到大，又因为需要用到（i-1, j，k）位置的状态，所以i的变化需要从小到大，此时j的变化可以从小到大，也可以从大到小。
     
 

 

返回值
 

状态表示为dp[i][j][k]表示，从前i个工作中挑选，总需人数不超过j，总利润不少于k，总盈利计划个数。
 

结合题目意思，我们需要在前m个工作中挑选，总需人数不超过n，总利润不少于minProfit，总盈利计划个数。
 

返回dp[m][n][minProfit]
 

（m表示工作个数）
 

代码实现
 

 

  1. class Solution {
  2. public:
  3.     int profitableSchemes(int n, int minProfit, vector<int>& group,
  4.                           vector<int>& profit) {
  5.         int m = group.size();
  6.         int MOD = 1e9 + 7;
  7.         vector<vector<vector<int>>> dp(
  8.             m + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
  9.  
  10.         for (int j = 0; j <= n; j++) {
  11.             dp[0][j][0] = 1;
  12.         }
  13.         for (int i = 1; i <= m; i++) {
  14.             for (int j = 0; j <= n; j++) {
  15.                 for (int k = 0; k <= minProfit; k++) {
  16.                     dp[i][j][k] = dp[i - 1][j][k];
  17.                     if (j - group[i - 1] >= 0)
  18.                         dp[i][j][k] = (dp[i][j][k]+dp[i - 1][j - group[i - 1]]
  19.                                          [max(0, k - profit[i - 1])])%MOD;
  20.                 }
  21.             }
  22.         }
  23.         return dp[m][n][minProfit];
  24.     }
  25. };
 

377. 组合总和 Ⅳ - 力扣（LeetCode）
 

 

题目解析
 

 

因此我们应该换一种思路，尝试正向解决这道问题。
 

 

在正向推导过程我们发现了重复子问题，求元素和为target一共有多少种排列方法数，等价于求元素和为target-第一个位置上的元素值，一共有多少种排列方法数，然后再考虑第一个位置上所有情况即可。
 

因此我们可以定义状态表示为dp[i]元素和为i的所有排列方法数。
 

状态表示
 

定义dp[i]元素和为i的所有排列方法数。
 

状态转移方程
 

  1.  
    如果有排列，
     
  
    1.  
      第一个位置为nums[0], 此时dp[i]=dp[i-nums[0]]。
       
    2.  
      第一个位置为nums[1], 此时dp[i]=dp[i-nums[1]]。
       
    3.  
      第一个位置为nums[2], 此时dp[i]=dp[i-nums[2]]。
       
    4.  
      .......
       
  2.  
    如果没排列， dp[0]=1。
     
 

 

综上所述，状态转移方程为，dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+..........
 

如果i-nums[0]<0，此时不存在。同时dp[0]=1。
 

 

  1.             for(auto j:nums){
  2.                 if(j<=i){
  3.                     dp[i]+=dp[i-j];
  4.                 }
  5.             }
 

初始化
 

根据状态转移方程，dp[i]+=，所以每个位置都需要初始化为0。而没有排列的时候，dp[0]=1。
 

填表顺序
 

根据状态转移方程，推导i位置状态需要用到i-j位置的状态，所以i的变化需要从小到大。
 

返回值
 

状态表示为，定义dp[i]元素和为i的所有排列方法数。
 

结合题目意思，我们需要返回dp[target]
 

代码实现
 

 

  1. class Solution {
  2. public:
  3.     int combinationSum4(vector<int>& nums, int target) {
  4.         vector<double>dp(target+1);
  5.         dp[0]=1;
  6.         for(int i=1;i<=target;i++){
  7.             for(auto j:nums){
  8.                 if(j<=i){
  9.                     dp[i]+=dp[i-j];
  10.                 }
  11.             }
  12.         }
  13.         return dp[target];
  14.     }
  15. };
 

96. 不同的二叉搜索树 - 力扣（LeetCode）
 

 

题目解析
 

 

状态表示
 

定义dp[i]表示节点数为i，组成的二叉搜索树种类数。
 

状态转移方程
 

  1.  
    当节点数至少为3时，假设j作为根节点。 此时左边是1~(j-1)，一共有（j-1）-1+1=j-1 个数， 右边是（j+1）~i，一共有i-（j+1）+1=i-j 个数，
     
      状态转移方程为，
     
     
    1. for(int j=1;j<=i;j++){
    2.         dp[i]+=dp[j-1]*dp[i-j];
    3.     }
     
  2.  
    当节点数为2时， dp[2]=2。
     
  3.  
    当节点数为1时， dp[1]=1。
     
  4.  
    当节点数为0时， dp[0]=1。此时表示没有节点，二叉搜索树的种类数，空也算是一种。表示左孩子为0时，种类数为右孩子种类数乘以1，或者右孩子为0时，种类数为左孩子种类数乘以1。
     
 

 

初始化
 

根据状态转移方程，dp[i]+=，所以每个状态先初始化为0。
 

填表顺序
 

根据状态转移方程，推导i位置状态时需要用到j-1，和i-j位置的状态，所以i的变化需要从小到大。
 

返回值
 

状态表示为，定义dp[i]表示节点数为i，组成的二叉搜索树种类数。
 

结合题目意思，我们需要返回dp[n]
 

代码实现
 

 

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         vector<int>dp(n+1);
  5.         if(n==0||n==1) return 1;
  6.         else if(n==2) return 2;
  7.         dp[0]=1;
  8.         dp[1]=1;
  9.         dp[2]=2;
  10.         for(int i=3;i<=n;i++){
  11.             for(int j=1;j<=i;j++){
  12.                 dp[i]+=dp[j-1]*dp[i-j];
  13.             }
  14.         }
  15.         return dp[n];
  16.         
  17.     }
  18. };
 

结尾
 

今天我们学习了动态规划的思想，动态规划思想和数学归纳法思想有一些类似，动态规划在模拟数学归纳法的过程，已知一个最简单的基础解，通过得到前项与后项的推导关系，由这个最简单的基础解，我们可以一步一步推导出我们希望得到的那个解，把我们得到的解依次存放在dp数组中，dp数组中对应的状态，就像是数列里面的每一项。最后感谢您阅读我的文章，对于动态规划系列，我会一直更新，如果您觉得内容有帮助，可以点赞加关注，以快速阅读最新文章。
 

 

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
 

 

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
 

 

谢谢您的支持，期待与您在下一篇文章中再次相遇！

                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/365919
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号