上海工程建设信息网官网,seo是指什么岗位,大连三川建设集团,谷歌搜索广告优化1--动态规划理论基础 动态规划经典问题#xff1a;① 背包问题#xff1b;② 打家劫舍#xff1b;③ 股票问题#xff1b; ④ 子序列问题#xff1b; 动态规划五部曲#xff1a; ① 确定 dp 数组及其下标的含义#xff1b; ② 确定递推公式#xff1b; ③ 确定 dp 数组…1--动态规划理论基础 动态规划经典问题① 背包问题② 打家劫舍③ 股票问题 ④ 子序列问题 动态规划五部曲 ① 确定 dp 数组及其下标的含义 ② 确定递推公式 ③ 确定 dp 数组的初始化 ④ 确定遍历顺序一般为从左到右 ⑤ 打印 dp 数组一般用于检查 2--斐波那契数 主要思路 经典动态规划dp[i] 表示第 i 个数的斐波那契数递推公式为dp[i] dp[i-1] dp[i - 2]初始化dp[0] 1dp[1] 1遍历顺序从左到右 #include iostream
#include vectorclass Solution {
public:int fib(int n) {if(n 1) return n;std::vectorint dp(n1, 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 vectorclass Solution {
public:int climbStairs(int n) {if(n 2) return n; std::vectorint dp(n1, 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 vectorclass Solution {
public:int minCostClimbingStairs(std::vectorint cost) {std::vectorint 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::vectorint 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] 1dp[0][j] 1状态转移方程为dp[i][j] dp[i-1][j] dp[i][j-1]遍历顺序为从上到下从左到右 #include iostream
#include vectorclass Solution {
public:int uniquePaths(int m, int n) {std::vectorstd::vectorint dp(m, std::vectorint(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] 1dp[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 vectorclass Solution {
public:int uniquePathsWithObstacles(std::vectorstd::vectorint obstacleGrid) {int m obstacleGrid.size(), n obstacleGrid[0].size();if(obstacleGrid[m-1][n-1] 1) return 0;std::vectorstd::vectorint dp(m, std::vectorint(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::vectorstd::vectorint 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 vectorclass Solution {
public:int integerBreak(int n) {std::vectorint dp(n1, 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 vectorclass Solution {
public:int numTrees(int n) {std::vectorint dp(n1, 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;
}
9--
