代码随想录笔记--动态规划篇
1--动态规划理论基础
动态规划经典问题：① 背包问题；② 打家劫舍；③ 股票问题； ④ 子序列问题；
动态规划五部曲：
① 确定 dp 数组及其下标的含义；
② 确定递推公式；
③ 确定 dp 数组的初始化；
④ 确定遍历顺序，一般为从左到右；
⑤ 打印 dp 数组，一般用于检查；
2--斐波那契数
主要思路：
经典动态规划，dp[i] 表示第 i 个数的斐波那契数；递推公式为：dp[i] = dp[i-1] + dp[i - 2]；初始化dp[0] = 1，dp[1] = 1；遍历顺序从左到右；
#include <iostream>
#include <vector>class Solution {
public:int fib(int n) {if(n <= 1) return n;std::vector<int> dp(n+1, 0);dp[0] = 0; dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};int main(int argc, char argv[]){int test = 2;Solution S1;int res = S1.fib(test);std::cout << res << std::endl;return 0;
}
3--爬楼梯
主要思路：
经典动态规划，dp[i] 表示到达第 i 阶楼梯的方法数；递推公式为 dp[i] = dp[i - 1] + dp[i - 2]；初始化dp[1] = 1, dp[2] = 2；遍历顺序从左到右；
#include <iostream>
#include <vector>class Solution {
public:int climbStairs(int n) {if(n <= 2) return n; std::vector<int> dp(n+1, 0);dp[1] = 1, dp[2] = 2;for(int i = 3; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};int main(int argc, char argv[]){int n = 2;Solution S1;int res = S1.climbStairs(n); std::cout << res << std::endl;return 0;
}
4--使用最小花费爬楼梯
主要思路：
dp[i] 表示到达第 i 阶楼梯需要的最小花费；初始化 dp[0] = 0, dp[1] = 0，因为可以从 0 和 1 出发，因此不需要花费；递推公式为 dp[i] = std::min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])；默认从左到右遍历；
#include <iostream>
#include <vector>class Solution {
public:int minCostClimbingStairs(std::vector<int>& cost) {std::vector<int> dp(cost.size()+1, 0); // 到达第i阶的最小花费dp[0] = 0;dp[1] = 0;for(int i = 2; i <= cost.size(); i++){dp[i] = std::min(cost[i-2]+dp[i-2], cost[i-1]+dp[i-1]);}return dp[cost.size()];}
};int main(int argc, char argv[]){// cost = [1,100,1,1,1,100,1,1,100,1]std::vector<int> cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};Solution S1;int res = S1.minCostClimbingStairs(cost);std::cout << res << std::endl;return 0;
}
5--不同路径
主要思路：
dp[i][j] 表示到达 (i, j) 位置的路径数，初始化两个边界 dp[i][0] = 1，dp[0][j] = 1；状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]；遍历顺序为从上到下，从左到右；
#include <iostream>
#include <vector>class Solution {
public:int uniquePaths(int m, int n) {std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));// 初始化for(int i = 0; i < m; i++) dp[i][0] = 1;for(int j = 0; j < n; j++) dp[0][j] = 1;// 遍历for(int r = 1; r < m; r++){for(int c = 1; c < n; c++){dp[r][c] = dp[r-1][c] + dp[r][c-1];}}return dp[m-1][n-1];}
};int main(int argc, char argv[]){// m = 3, n = 7int m = 3, n = 7;Solution S1;int res = S1.uniquePaths(m, n);std::cout << res << std::endl;return 0;
}
6--不同路径II
主要思路：
与上题类似，dp[i][j] 表示到达 (i, j) 位置的路径数，初始化两个边界 dp[i][0] = 1，dp[0][j] = 1（确保边界没有障碍物，有障碍物初始化为0）；状态转移方程为：(i, j)不是障碍物则 dp[i][j] = dp[i-1][j] + dp[i][j-1]，(i, j)为障碍物则dp[i][j] = 0；遍历顺序为从上到下，从左到右；
#include <iostream>
#include <vector>class Solution {
public:int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();if(obstacleGrid[m-1][n-1] == 1) return 0;std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));// 初始化for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++) dp[i][0] = 1;for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++) dp[0][j] = 1;// 遍历for(int r = 1; r < m; r++){for(int c = 1; c < n; c++){if(obstacleGrid[r][c] == 1) dp[r][c] = 0; // 障碍else dp[r][c] = dp[r-1][c] + dp[r][c-1];}}return dp[m-1][n-1];}
};int main(int argc, char argv[]){// obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]std::vector<std::vector<int>> test = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};Solution S1;int res = S1.uniquePathsWithObstacles(test);std::cout << res << std::endl;return 0;
}
7--整数拆分
主要思路：
dp[i] 表示整数 i 拆分后的最大乘积；初始化dp[0] = 0, dp[1] = 0, dp[2] = 1; 状态转移方程为：dp[i] = max(dp[i], max(j*(i-j), j * dp[i-j]))；
#include <iostream>
#include <vector>class Solution {
public:int integerBreak(int n) {std::vector<int> dp(n+1, 0);// 初始化dp[0] = 0, dp[1] = 0, dp[2] = 1;// 遍历for(int i = 3; i <= n; i++){for(int j = 0; j <= i/2; j++){dp[i] = std::max(dp[i], std::max(j*(i-j), j * dp[i-j]));}}return dp[n];}
};int main(int argc, char argv[]){// n = 10int test = 10;Solution S1;int res = S1.integerBreak(test);std::cout << res << std::endl;return 0;
}
8--不同的二叉搜索树
主要思路：
dp[i] 表示由 i 个数字构成的不同二叉搜索树的数目；
初始化：dp[0] = 1；
状态转移方程：dp[i] += dp[j-1] * dp[i-j]，0 <= j <= i；其中 dp[j-1] 来构成 j 的左子树，dp[i-j] 来构成 j 的右子树；
遍历顺序：两个 for 循环，第 1 个 for 循环遍历 1 - n，第二个 for 循环遍历 1 - i；
#include <iostream>
#include <vector>class Solution {
public:int numTrees(int n) {std::vector<int> dp(n+1, 0);// 初始化dp[0] = 1;// 遍历for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
};int main(int argc, char *argv[]) {// n = 3int test = 3;Solution S1;int res = S1.numTrees(test);std::cout << res << std::endl;return 0;
}