参考文章动态规划入门 闫氏DP分析法从此再也不怕DP问题_哔哩哔哩_bilibili动态规划就是 : 给定一个问题我们把它拆成一个个子问题直到子问题可以直接解决。然后把子问题的答案保存起来以减少重复计算记忆化搜索。再根据子问题答案反推得出原问题解的一种方法.主要方法:1.设计一个数据结构记录不同规模问题的答案2.数据结构采用从小到大的生成方式去生成一般流程 1.大问题到小问题的拆分 2.找到最小问题 3.记录最小问题回推到大问题动态规划入门思路: dfs暴力 --- 记忆化搜索 --- 递推1dfs 2记忆化搜索 3逆序递推 4顺序递推 5优化空间题目821. 跳台阶 - AcWing题库记忆化搜索 dfs暴力记忆存储重复结果递推 dfs的向下递归的公式 递推的边界为递归的边界题目821. 跳台阶 - AcWing题库#includebits/stdc.h using namespace std; const int N 100; int n; int f[N]; //递推公式 int main(){ scanf(%d,n); f[1]1,f[2] 2; if(n1||n2){ f[1]1,f[2]2; printf(%d\n,f[n]); return 0; } for(int i 3;in;i){ f[i] f[i-1]f[i-2]; } printf(%d\n,f[n]); return 0; }//dp递推2.分苹果3428. 放苹果 - AcWing题库 //统计方案数题型初始值为1相加思路动态规划把n 个苹果放到m 个盘子当中去除重合的情况数组f[i][j] 表示 把i个苹果放到j个盘子当中 f[0][0] 1表示空拆分递推的起点分情况1.如果ij(也就是苹果的数量大于盘子数量) 则 先把每个盘子都放一个苹果 然后剩下i-j个苹果在放随便放j个盘子当中 f[i][j] f[i][j-1] f[i-j][j]; j-1表示方案数减1f[i-j][j]表示还剩下i-j个元素 有j种方案2.如果苹果数量少于盘子数量 那么就只有苹果数量这么多种方法 f[i][j] f[i][i]#includeiostream #includealgorithm #includecstring using namespace std; const int N 15; int f[N][N];//全局定义数组不用初始化 int main(){ int n,m; while(cinnm){ f[0][0]1;//不进行拆分也是一种方案是所有分拆方案的 “起点” 和 “边界条件” // memset(f,1,sizeof f); for(int i 0;in;i){ for(int j 0;jm;j){ if(ij) f[i][j] f[i][j-1]f[i-j][j];//当苹果的数量大于盘中的时候 //可以把每个盘子都放一遍 剩下的苹果可以放任意的j个盘子 else f[i][j] f[i][i];//苹果小于盘子时只能放苹果数量这么多方案 } } printf(%d\n,f[n][m]);//解决把n个苹果放到m个盘子中的方案数量 } return 0; }2.最长公共子序列(一)_牛客题霸_牛客网最长公共子序列长度子序列不要求字符连续但顺序必须一致核心思路动态规划的状态定义和状态转移1.dp[i][j] 表示 s1 字符串前i个字符和s2字符串前j个字符的最长公共子序列的长度2.二维数组初始化空串和任何字符串的公共子序列只能是空串长度自然为 0for(int i 0;in;i) dp[i][0] 0; // s2前0个字符空串和任意s1前i个字符的LCS长度为0 for(int j 0;jm;j) dp[0][j] 0; // s1前0个字符空串和任意s2前j个字符的LCS长度为03.状态转移分两种情况1.字符匹配相等(dp[i][j] dp[i-1][j-1]1;因为字符前i-1和j-1个相匹配后面进行在原基础上长度加1 ) 2. 字符匹配不相等不能直接加上去而是去除s1,s2的当前最大值的字符if(s1[i-1]s2[j-1]) dp[i][j] dp[i-1][j-1]1; // 字符相等的情况 else dp[i][j] max(dp[i-1][j], dp[i][j-1]); // 字符不相等的情况4.dp[n][m] 长度为n的字符串s1和长度为m的字符串s2的长度的最长公共子序列的长度大小#includeiostream #includealgorithm #includecstring using namespace std; const int N 1020; int dp[N][N]; int n,m; char s1[N],s2[N]; int main(){ cinnm; cins1s2; //二维数组初始化 for(int i 0;in;i) dp[i][0] 0; for(int j 0;jm;j) dp[0][j] 0; //匹配的条件 for(int i 1;in;i){ for(int j 1;jm;j){ if(s1[i-1]s2[j-1]) dp[i][j] dp[i-1][j-1]1; else dp[i][j] max(dp[i-1][j],dp[i][j-1]); } } //打印 coutdp[n][m]; return 0; }附件问题 然后输出最短公共子序列是什么思路定义一个lcs字符串 进行拼接 如果s1 s2 则拼接并且i--,j--,如果不相等 则 将dp长度大的减1 最后将lcs使用reverse反转一下//逻辑实现 从子串后面往前遍历 最后做一个反转reverse int i n,jm; while(i0j0){ if(s1[i-1]s2[j-1]){ LCAs1[i]-1; i--;j--; } else if(dp[i-1][j]dp[i][j-1])//dp长度比较 如果i的长度大则减1 否则 j 减1 i--; else j--; } reverse(LCS.begin(), LCS.end()); cout最长公共子序列长度dp[n][m]endl; cout最长公共子序列为LCS;2.求解最长公共子串3508. 最长公共子串 - AcWing题库使用二维数组空间大 则使用一维数组替换的核心思路“复用” 空间既然计算dp[i][j]只需要dp[i-1][j-1]我们可以用一维数组dp[j]来 “复用” 存储初始时dp[j]存储的是上一行i-1 行的所有结果计算当前行i 行的dp[j]时我们需要的是上一行的dp[j-1]即原dp[i-1][j-1]#includeiostream #includecstring #includealgorithm #includestring #includecctype //isalpha 的头文件 using namespace std; const int N 10010; int dp[N]; char s1[N],s2[N]; int curmax 0; int main(){ cins1s2; int s1len strlen(s1); int s2len strlen(s2); memset(dp,0,sizeof dp);//初始化 for(int i 1 ;is1len;i){ for(int j s2len;j0;j--){//倒序输出 if(s1[i-1]s2[j-1]isalpha(s1[i-1])isalpha(s2[j-1])){ dp[j] dp[j-1]1;//用一维数组记录 curmax max(dp[j],curmax);//取最大值 } else dp[j] 0; } } printf(%d\n,curmax); return 0; }3. 最大序列和3393. 最大序列和 - AcWing题库思路dp 情况case1 :如果 d[i-1] 0 则下一位d[i] s[i-1]返回是一个位置’case2如果 d[i-1]0 则下一位d[i] s[i-1] d[i-1]直接加上其和使用curmax 进行存放每次的最大值#includeiostream #includealgorithm #includecstring using namespace std; const long long N 100000010; long long dp[N];//dp[i] 表示以s[i-1]为结尾的连续子数组的最大和 int n; long long s[N]; int main(){ scanf(%d,n); for(int i 0;in;i) scanf(%lld,s[i]);//输入数字 dp[1] s[0];//dp[1] 以s[0]第一个元素结尾的最大子数组和就是它本 long long curmax dp[1];//初始化 //状态转移 for(int i 2;in;i){ if(dp[i-1]0) //case1 dp[i-1]0 会拉低和的值不如重新开始 dp[i] s[i-1]; else dp[i] s[i-1] dp[i-1];//接上它能让当前和更大直接累加 curmax max(curmax,dp[i]); } coutcurmax; return 0; }4.最大上升子序列和 最大上升子序列和_牛客题霸_牛客网思路dp状态转移条件dp数组是以num[i]为结尾的数组前面上升序列和if(num[i]num[j])dp[i] max(dp[i],dp[j]num[i]);//记录更新大小的值 dp[j] num[i]表示接上这个数之后在所有能接的j里选一个让dp[i]最大的结果保证dp[i]始终是 “以num[i]结尾的最大和”。#includeiostream #includealgorithm #includecstring using namespace std; const int N 1010; int dp[N];//dp记录 int num[N]; int n; int main(){ while(cinn){ for(int i 0;in;i) scanf(%d,num[i]);//初始化数组 int ans 0; //初始ans for(int i 0;in;i){//遍历循环 dp[i] num[i];//初始化 for(int j 0;ji;j){ if(num[i]num[j]){//判断条件 dp[i] max(dp[i],dp[j]num[i]);//记录更新大小的值 } ans max(ans,dp[i]); //更新最值 } } coutansendl; } return 0; }