0
0

动态规划：基础篇

1. 斐波那契数(LeetCode509)

题目描述：https://leetcode.cn/problems/fibonacci-number/description/

解法1：动态规划(基础版)

解题思路：动态规划五部曲

  • Step1：确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]：第i个数的斐波那契数值是dp[i]
  • Step2：确定递推公式 - dp[i] = dp[i - 1] + dp[i - 2] 题目已给
  • Step3：初始化dp数组 - 由递推公式可知，需要初始化前两个元素（题目已给） - dp[0] = 0- dp[1] = 1
  • Step4：确定遍历顺序 - 由递推公式可知，后面的斐波那契数值依赖于前面两个- 因此，需要从前向后遍历
  • Step5：打印dp数组（调试）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution 
  6. {
  7. public:
  8.     int fib(int n) 
  9.     {
  10.         if (n <= 1) return n;
  12.         // Step3：初始化dp数组
  13.         vector<int> dp(n + 1);
  14.         dp[0] = 0;
  15.         dp[1] = 1;
  16.         // Step4：确定遍历顺序
  17.         for (int i = 2; i <= n; i++)
  18.         {
  19.             // Step2：确定递推公式
  20.             dp[i] = dp[i - 1] + dp[i - 2];
  21.         }
  22.         return dp[n];
  23.     }
  24. };
  26. int main()
  27. {
  28.     int n = 4;
  30.     Solution s;
  31.     int ans = s.fib(n);   // 3
  33.     cout << ans << endl;
  35.     system("pause");
  36.     return 0;
  37. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算每个元素的斐波那契数值
  • 空间复杂度：O(n) 需要存储每个元素的斐波那契数值

注意事项：

  • if (n <= 1) return n; 当n为0或1时，无法由递推公式推导得到，需要根据dp数组的含义直接返回结果，此处在实际编程过程中容易忽略。（所有动态规划题目都需要格外注意）

解法2：动态规划(优化版)

解题思路：利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值，因此只需要维护两个数值 （后面将讲解的很多动规的题目其实都是当前状态依赖前两个，或者前三个状态，都可以做空间上的优化）

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  4.   
  5. class Solution
  6. {
  7. public:
  8.     int fib(int n)
  9.     {
  10.         if (n <= 1) return n;
  12.         vector<int> dp(2, 0);  // 优化：只需要维护两个数值即可，不需要记录整个序列
  13.         dp[0] = 0;
  14.         dp[1] = 1;
  15.         for (int i = 2; i <= n; i++)
  16.         {
  17.             int sum = dp[0] + dp[1];
  18.             dp[0] = dp[1];
  19.             dp[1] = sum;
  20.         }
  21.         return dp[1];
  22.     }
  23. };
  25. int main()
  26. {
  27.     int n = 4;
  29.     Solution s;
  30.     int ans = s.fib(n);   // 3
  32.     cout << ans << endl;
  34.     system("pause");
  35.     return 0;
  36. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算每个元素的斐波那契数值
  • 空间复杂度：O(1) 无需存储每个元素的斐波那契数值（只需要维护两个数值即可，不需要记录整个序列）

2. 爬楼梯(方案个数)(斐波那契数列扩展)(LeetCode70)

题目描述：https://leetcode.cn/problems/climbing-stairs/description/

解法1：动态规划(基础版)

解题思路：动态规划五部曲
爬到第1层楼梯：有1种方法
爬到第2层楼梯：有2种方法 1+1(每次爬一个台阶)、2(一次爬两个台阶)
爬到第3层楼梯：有3种方法
1 +2(先爬一个台阶、再爬两个台阶) 由第1层楼梯过来
1+1 +1(每次爬一个台阶) 由第2层楼梯过来
2 +1(先爬两个台阶、再爬一个台阶) 由第2层楼梯过来
可见，到第三层楼梯的状态 可以由 第二层楼梯 和 第一层楼梯状态 推导出来

  • Step1：确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]：爬到第i层楼梯的方法个数有dp[i]种
  • Step2：确定递推公式 - 从dp[i]的定义可以看出，dp[i]可以有两个方向推出来 - dp[i-1]：上到第i-1层楼梯，有dp[i-1]种方法，再一步 跳一个台阶 即可到达第i层楼梯- dp[i-2]：上到第i-2层楼梯，有dp[i-2]种方法，再一步 跳两个台阶 即可到达第i层楼梯- dp[i] = dp[i-1] + dp[i-2]
  • Step3：初始化dp数组 - 由递推公式可知，需要初始化前两个元素 - dp[1] = 1- dp[2] = 2- 注意：此处并不初始化dp[0]，因为没有实际意义- 很多题解强行将dp[0]初始化为1，基本都是直接奔着答案去解释的（因为在递推的过程中i从2开始遍历本题就能过）
  • Step4：确定遍历顺序 - 由递推公式可知，需要从前向后遍历
  • Step5：打印dp数组（调试）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution 
  6. {
  7. public:
  8.     int climbStairs(int n) 
  9.     {
  10.         if (n <= 2) return n;
  12.         vector<int> dp(n+1);
  13.         dp[1] = 1;
  14.         dp[2] = 2;
  15.         for (int i = 3; i <= n; i++)  // 注意：此处i是从3开始遍历
  16.         {
  17.             dp[i] = dp[i - 1] + dp[i - 2];
  18.         }
  19.         return dp[n];
  20.     }
  21. };
  23. int main()
  24. {
  25.     Solution s;
  26.     int ans = s.climbStairs(3);
  28.     cout << ans << endl;
  30.     system("pause");
  31.     return 0;
  32. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算到达每层楼梯的方法个数
  • 空间复杂度：O(n) 需要存储到达每层楼梯的方法个数

解法2：动态规划(优化版)

解题思路：利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值，因此只需要维护两个数值 （动态规划的常见优化思路）

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public:
  8.     int climbStairs(int n)
  9.     {
  10.         if (n <= 2) return n;
  12.         vector<int> dp(3);
  13.         dp[1] = 1;
  14.         dp[2] = 2;
  15.         for (int i = 3; i <= n; i++)  // 注意：此处i是从3开始遍历
  16.         {
  17.             int sum = dp[1] + dp[2];
  18.             dp[1] = dp[2];
  19.             dp[2] = sum;
  20.         }
  21.         return dp[2];
  22.     }
  23. };
  25. int main()
  26. {
  27.     Solution s;
  28.     int ans = s.climbStairs(3);
  30.     cout << ans << endl;
  32.     system("pause");
  33.     return 0;
  34. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算到达每层楼梯的方法个数
  • 空间复杂度：O(1) 无需存储每个元素的斐波那契数值（只需要维护两个数值即可，不需要记录整个序列）

3. 爬楼梯(最小花费)(LeetCode746)

题目描述：https://leetcode.cn/problems/min-cost-climbing-stairs/

解法1：动态规划(基础版)

解题思路：动态规划五部曲

  • Step1：确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]：到达第i台阶所花费的最少体力为dp[i]
  • Step2：确定递推公式 - 由于每次只能向上爬一个或者两个台阶，因此到达第i台阶有两个途径 - 从第i-1台阶跳1步：需要花费 dp[i-1]+cost[i-1]- 从第i-2台阶跳2步：需要花费 dp[i-2]+cost[i-2]- dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  • Step3：初始化dp数组 - 题目描述：可以选择从下标为0或下标为1的台阶开始爬楼梯- 到达第0个台阶是不花费体力，但从第0个台阶往上跳的话，需要花费cost[0]- 到达第1个台阶是不花费体力，但从第1个台阶往上跳的话，需要花费cost[1]- dp[0] = 0- dp[1] = 0
  • Step4：确定遍历顺序 - 由递推公式可知，需要从前向后遍历
  • Step5：打印dp数组（调试）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution 
  6. {
  7. public:
  8.     int minCostClimbingStairs(vector<int>& cost) 
  9.     {
  10.         vector<int> dp(cost.size()+1);
  11.         dp[0] = 0;
  12.         dp[1] = 0;
  14.         for (int i = 2; i <= cost.size(); i++)
  15.         {
  16.             dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  17.         }
  18.         return dp[cost.size()];
  19.     }
  20. };
  22. int main()
  23. {
  24.     vector<int> cost{ 10,15,20 };   // 15
  25.     //vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 };   // 6
  27.     Solution s;
  28.     int ans = s.minCostClimbingStairs(cost);
  30.     cout << ans << endl;
  31. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算到达每层楼梯的最小体力
  • 空间复杂度：O(n) 需要存储到达每层楼梯的最小体力

解法2：动态规划(优化版)

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public:
  8.     int minCostClimbingStairs(vector<int>& cost)
  9.     {
  10.         vector<int> dp(2);
  11.         dp[0] = 0;
  12.         dp[1] = 0;
  14.         for (int i = 2; i <= cost.size(); i++)
  15.         {
  16.             int dpi = min(dp[0] + cost[i-2], dp[1] + cost[i-1]);
  17.             dp[0] = dp[1];
  18.             dp[1] = dpi;
  19.         }
  20.         return dp[1];
  21.     }
  22. };
  24. int main()
  25. {
  26.     vector<int> cost{ 10,15,20 };   // 15
  27.     //vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 };   // 6
  29.     Solution s;
  30.     int ans = s.minCostClimbingStairs(cost);
  32.     cout << ans << endl;
  33. }

复杂度分析：

  • 时间复杂度：O(n) 需要计算到达每层楼梯的最小体力
  • 空间复杂度：O(1)

4. 不同路径(无障碍)(LeetCode62)

题目描述：https://leetcode.cn/problems/unique-paths/description/

解法1：动态规划(基础版)

解题思路：动态规划五部曲

  • Step1：确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i][j]：从(0,0)出发到达(i,j)的不同路径有dp[i][j]条
  • Step2：确定递推公式 - 机器人每次只能向下或者向右移动一步，因此到达(i,j)有两个途径 - 从(i-1,j)向下移动：dp[i-1][j] 从(0,0)出发，到(i-1,j)的不同路径个数- 从(i,j-1)向右移动：dp[i][j-1] 从(0,0)出发，到(i,j-1)的不同路径个数- dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  • Step3：初始化dp数组 - 从(0,0)出发，到达第一行的任意位置，只有1种路径 → dp[0][j] = 1- 从(0,0)出发，到达第一列的任意位置，只有1种路径 → dp[i][0] = 1- 注意：只能向下或向右移动
  • Step4：确定遍历顺序 - 由递推公式可知，需要从前向后、从上向下遍历
  • Step5：打印dp数组（调试）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public:
  8.     int uniquePaths(int m, int n) 
  9.     {
  10.         // 示例：m=3 n=7
  11.         // 1  1  1  1  1  1  1
  12.         // 1  2  3  4  5  6  7
  13.         // 1  3  6  10 15 21 28
  15.         // Step3：初始化dp数组
  16.         vector<vector<int>> dp(m, vector<int>(n, 0));   // 二维数组的初始化（重要）
  17.         for (int i = 0; i < m; i++)  dp[i][0] = 1;
  18.         for (int j = 0; j < n; j++) dp[0][j] = 1;
  19.         // Step4：确定遍历顺序
  20.         for (int i = 1; i < m; i++)
  21.         {
  22.             for (int j = 1; j < n; j++)
  23.             {
  24.                 // Step2：确定递推公式
  25.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  26.             }
  27.         }
  28.         return dp[m - 1][n - 1];
  29.     }
  30. };
  32. int main()
  33. {
  34.     Solution s;
  35.     int ans = s.uniquePaths(3, 7);  // 28
  37.     cout << ans << endl;
  39.     system("pause");
  40.     return 0;
  41. }

复杂度分析：

  • 时间复杂度：O(m×n) 需要计算到达每一个位置的不同路径个数，两层for循环（第一层for循环遍历m-1行，第二层for循环遍历n-1列）
  • 空间复杂度：O(m×n) 需要存储到达每一个位置的不同路径个数

解法2：动态规划(优化版)

解题思路：使用一维数组(可以理解为滚动数组)进行空间优化 → 不利于理解，但可以优化空间

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public:
  8.     int uniquePaths(int m, int n)
  9.     {
  10.         // 示例：m=3 n=7
  11.         // 初始化一维数组    1  1  1  1  1  1  1
  12.         // i=1              1  2  3  4  5  6  7
  13.         // i=2              1  3  6  10 15 21 28
  15.         // Step3：初始化dp数组
  16.         vector<int> dp(n, 1);
  17.         // Step4：确定遍历顺序(只能先遍历行，后遍历列)
  18.         for (int i = 1; i < m; i++)       // 遍历行时，只能从上向下遍历
  19.         {
  20.             for (int j = 1; j < n; j++)   // 遍历列时，只能从前向后遍历
  21.             // for (int j = n-1; j > 0; j--)  // 错误
  22.             {
  23.                 // Step2：确定递推公式
  24.                 // dp[j-1]：在计算dp[j]时，dp[j-1]已经计算完毕，因此dp[j-1]为第i行("新值") → 从(i,j-1)出发，向右移动
  25.                 // dp[j](公式右侧)：dp[j]还没有计算，因此dp[j]为第i-1行("旧值") → 从(i-1,j)出发，向下移动
  26.                 dp[j] = dp[j - 1] + dp[j];
  27.             }
  28.         }
  29.         return dp[n - 1];
  30.     }
  31. };
  33. int main()
  34. {
  35.     Solution s;
  36.     int ans = s.uniquePaths(3, 7);  // 28
  38.     cout << ans << endl;
  40.     system("pause");
  41.     return 0;
  42. }

复杂度分析：

  • 时间复杂度：O(m×n) 需要计算到达每一个位置的不同路径个数
  • 空间复杂度：O(n) 每一阶段仅存储一行中所有位置的信息（先计算完一行，再计算下一行）

5. 不同路径(有障碍)(LeetCode63)

题目描述：https://leetcode.cn/problems/unique-paths-ii/description/

解法1：动态规划(基础版)

解题思路：本题与不同路径（无障碍）的区别

  • 区别1：dp数组的初始化- 不同路径1：直接将第一行和第一列初始化为1- 不同路径2：若某个位置存在障碍物，则该位置及其之后的所有位置均不可达
  • 区别2：递推公式- 不同路径1：所有位置都可以计算递推公式- 不同路径2：若某个位置存在障碍物，则该位置的不同路径个数为0，无需计算递推公式，而是直接使用默认值（遇到障碍dp[i][j]保持0）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution 
  6. {
  7. public:
  8.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
  9.     {
  10.         int m = obstacleGrid.size();     // 网格的行数
  11.         int n = obstacleGrid[0].size();  // 网格的列数
  13.         // 若起点或终点存在障碍物，则表明终点不可达，直接返回路径个数0
  14.         if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
  16.         // Step3：初始化dp数组
  17.             // 若第一行存在障碍物，则该障碍物及其之后的所有位置均不可达；若第一行不存在障碍物，则所有位置均初始化为1
  18.             // 若第一列存在障碍物，则该障碍物及其之后的所有位置均不可达；若第一列不存在障碍物，则所有位置均初始化为1
  19.         // 注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况，就停止dp[i][0]的赋值1的操作，dp[0][j]同理
  20.         vector<vector<int>> dp(m, vector<int>(n, 0));
  21.         for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;      // 初始化第一列
  22.         for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;      // 初始化第一行
  24.         // Step4：确定遍历顺序
  25.         for (int i = 1; i < m; i++)
  26.         {
  27.             for (int j = 1; j < n; j++)
  28.             {
  29.                 // Step2：确定递推公式
  30.                 // 当前位置不存在障碍物，执行if语句，计算达到该位置的不同路径个数
  31.                 // 当前位置存在障碍物，不执行if语句，使用默认的初始化值0，表明该位置不可达 或 达到该位置的不同路径个数为0
  32.                 if (obstacleGrid[i][j] == 0)
  33.                 {
  34.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  35.                 }
  36.             }
  37.         }
  38.         return dp[m - 1][n - 1];
  39.     }
  40. };
  42. int main()
  43. {
  44.     vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} };  // 2
  45.     //vector<vector<int>> obstacleGrid{ {0,1},{0,0} };  // 1
  47.     Solution s;
  48.     int ans = s.uniquePathsWithObstacles(obstacleGrid);
  50.     cout << ans << endl;
  52.     system("pause");
  53.     return 0;
  54. }

复杂度分析：

  • 时间复杂度：O(mxn)
  • 空间复杂度：O(mxn)

注意事项：

  • if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0; 若起点或终点存在障碍物，则表明终点不可达，直接返回路径个数0（易漏点）

解法2：动态规划(优化版)

  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public:
  8.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
  9.     {
  10.         int m = obstacleGrid.size();     // 网格的行数
  11.         int n = obstacleGrid[0].size();  // 网格的列数
  13.         // 若起点或终点存在障碍物，则表明终点不可达，直接返回路径个数0
  14.         if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
  16.         // Step3：初始化dp数组
  17.         vector<int> dp(n, 0);
  18.         for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;
  20.         // Step4：确定遍历顺序
  21.         for (int i = 1; i < m; i++)
  22.         {
  23.             for (int j = 0; j < n; j++)
  24.             {
  25.                 // Step2：确定递推公式
  26.                 // 对于第1列：若存在障碍物，则赋值为0；若不存在障碍物，保持不变
  27.                 // 对于其余列：若存在障碍物，则赋值为0；若不存在障碍物，则利用递推公式推导              
  28.                 if (obstacleGrid[i][j] == 1)   // 若存在障碍物(无论哪一列)，则赋值为0
  29.                 {
  30.                     dp[j] = 0;
  31.                 }
  32.                 else if(j != 0)                // 若不存在障碍物且非第1列，则利用递推公式
  33.                 {
  34.                     dp[j] = dp[j - 1] + dp[j];
  35.                 }
  36.                 // 注：以上代码不能修改如下
  37.                 // if (obstacleGrid[i][j] == 1) dp[j] = 0;   // 若存在障碍物，则赋值为0
  38.                 // if (j != 0) dp[j] = dp[j - 1] + dp[j];    // 若不存在障碍物，则利用递推公式（第一列不存在障碍物，则延续上一行的结果，不需要任何操作）
  39.             }
  40.         }
  41.         return dp[n - 1];
  42.     }
  43. };
  45. int main()
  46. {
  47.     vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} };  // 2
  48.     //vector<vector<int>> obstacleGrid{ {0,1},{0,0} };  // 1
  50.     Solution s;
  51.     int ans = s.uniquePathsWithObstacles(obstacleGrid);
  53.     cout << ans << endl;
  55.     system("pause");
  56.     return 0;
  57. }

复杂度分析：

  • 时间复杂度：O(mxn)
  • 空间复杂度：O(n)

6. 整数拆分(LeetCode343)

待补充！！！

7. 不同的二叉搜索树(LeetCode96)

题目描述： https://leetcode.cn/problems/unique-binary-search-trees/description/

以"n=3"举例分析

  • 当1为头结点时：右子树有两个节点，两个节点的布局 和 n=2时两棵树的布局 是一样的
  • 当2为头结点时：左右子树都只有一个节点，一个节点的布局 和 n=1时只有一棵树的布局 是一样的
  • 当3为头结点时：左子树有两个节点，两个节点的布局 和 n=2时两棵树的布局 是一样的 - dp[3]：元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量- 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量dp[2] * 左子树有0个元素的搜索树数量dp[0]- 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量dp[1] * 左子树有1个元素的搜索树数量dp[1]- 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量dp[0] * 左子树有2个元素的搜索树数量dp[2]- dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

解题思路：动态规划五部曲

  • Step1：确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]：由i个节点组成的二叉搜索树的个数为dp[i]
  • Step2：确定递推公式 - 假设头节点的数值为j（需要遍历头节点的所有可能）- dp[j-1]：由j-1个节点组成的二叉搜索树的个数（左子树的节点个数为j-1）- dp[i-j]：由i-j个节点组成的二叉搜索树的个数（右子树的节点个数为i-j）
  • Step3：初始化dp数组 - dp[0] = 1- dp[1] = 1 - dp[2] = 2
  • Step4：确定遍历顺序 - 从递推公式可以看出，i是由j-1和i-j推导而来，因此需要从前向后遍历- j从1遍历到i：j-1小于i；i-j小于i，因此i由小于i的项推导得到
  • Step5：打印dp数组（调试）
  1. #include <iostream>
  2. using namespace std;
  3. #include <vector>
  5. class Solution
  6. {
  7. public: 
  8.     int numTrees(int n) 
  9.     {
  10.         if (n == 1) return 1;
  11.         if (n == 2) return 2;
  13.         vector<int> dp(n + 1, 0);
  14.         dp[0] = 1;  // 易错点：dp[0]不能为0，否则会导致左右子树的布局个数相乘为0
  15.         dp[1] = 1;
  16.         dp[2] = 2;
  18.         for (int i = 3; i <= n; i++)      // 第一层for循环：遍历二叉搜索树中的节点个数
  19.         {
  20.             for (int j = 1; j <= i; j++)  // 第二层for循环：遍历头节点的数值（状态）
  21.             {
  22.                 dp[i] += (dp[j - 1] * dp[i - j]);
  23.             }
  24.         }
  25.         return dp[n];
  26.     } 
  27. };
  29. int main()
  30. {
  31.     //int n = 3;  // 5
  32.     int n = 1;  // 1
  34.     Solution s;
  35.     int ans = s.numTrees(n);
  37.     cout << ans << endl;
  39.     system("pause");
  40.     return 0;
  41. }

注意事项：当结点个数为0时，是否需要初始化，应该初始化为什么？这是一个难点(易错点、易漏点)。

  • dp[0] = 1; dp[0]不能为0，否则会导致左右子树的布局个数相乘为0
  • 本题的解法不能进行状态压缩，因为每次计算dp[i]时，需要依赖前面的所有状态。
标签： 动态规划 算法
本文转载自: https://blog.csdn.net/weixin_39549734/article/details/140842868
版权归原作者 华科大胡子 所有， 如有侵权，请联系我们删除。
登录后发布评论

“动态规划：基础篇”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？