网站页头制作,杭州网站设计首选柚米,百度开户代理,wordpress 报表算法学习18#xff1a;动态规划 文章目录 算法学习18#xff1a;动态规划前言一、线性DP1.数字三角形#xff1a;f[i][j] max(f[i - 1][j - 1] a[i][j], f[i - 1][j] a[i][j]);2.1最长上升子序列#xff1a;f[i] max(f[i], f[j] 1);2.2 打印出最长子序列3.最长公共子序…算法学习18动态规划 文章目录 算法学习18动态规划前言一、线性DP1.数字三角形f[i][j] max(f[i - 1][j - 1] a[i][j], f[i - 1][j] a[i][j]);2.1最长上升子序列f[i] max(f[i], f[j] 1);2.2 打印出最长子序列3.最长公共子序列 二、区间dp1.石子合并 总结 前言 提示以下是本篇文章正文内容
一、线性DP
1.数字三角形f[i][j] max(f[i - 1][j - 1] a[i][j], f[i - 1][j] a[i][j]); // 给定一个数字三角形从顶部出发在每一个结点可以选择移动至左下方或者是右下方的结点
// 直到移动到底层要求找到一条路径使得路径上的数字的和最大。
// 输入第一行包含一个整数n表示数字三角形的层数
// 接下来的n行每行包含若干整数其中第i行表示数字三角形第i层包含的整数。#include iostream
#include algorithmusing namespace std;const int N 510, INF 1e9;// (相对的)正无穷 int n;
int a[N][N];// 存出数字三角形
int f[N][N];// 状态 int main()
{scanf(%d, n);for(int i 1; i n; i )for(int j 1; j i; j )scanf(%d, a[i][j]);// 初始化// 注意1对于左右边界都要多处理一次。i1 for(int i 0; i n; i )for(int j 0; j i 1; j )f[i][j] -INF;// 负无穷 f[1][1] a[1][1];for(int i 2; i n; i )for(int j 1; j i; j )f[i][j] max(f[i - 1][j - 1] a[i][j], f[i - 1][j] a[i][j]);int res -INF;// 遍历最后一层找到答案 for(int i 1; i n; i ) res max(res, f[n][i]);printf(%d\n, res);return 0;} 2.1最长上升子序列f[i] max(f[i], f[j] 1); 2.2 打印出最长子序列 // 给定一个长度为n的数列求数值“严格递增”的子序列的长度最长时多少#include iostream
#include algorithmusing namespace std;const int N 1010;int n;
int a[N], f[N], g[N];// 数列 状态 存储i是由那个状态转移过来的。 int main()
{scanf(%d, n);for(int i 1; i n; i ) scanf(%d, a[i]);for(int i 1; i n; i ){f[i] 1;// 只有a[i]一个数g[i] 0; for(int j 1; j i; j )// 保证递增a[j] 是 a[i] 的前一个数 if(a[j] a[i])if(f[i] f[j] 1){// 更新 f[i] f[j] 1;// 记录一下f[i] 是从哪一个状态转移过来的。 g[i] j;} }// 找到答案的下标 int k 1;for(int i 1; i n; i )if(f[k] f[i]) k i;printf(%d\n, f[k]);// 长度 for(int i 0, len f[k]; i len; i ){printf(%d , a[k]);// 根据g数组可以知道f[k]是从那个状态转移的 k g[k];}return 0;
}// 给定一个长度为n的数列求数值“严格递增”的子序列的长度最长时多少#include iostream
#include algorithmusing namespace std;const int N 1010;int n;
int a[N], f[N];// 数列 状态 int main()
{scanf(%d, n);for(int i 1; i n; i ) scanf(%d, a[i]);for(int i 1; i n; i ){f[i] 1;// 只有a[i]一个数for(int j 1; j i; j )// 保证递增a[j] 是 a[i] 的前一个数 if(a[j] a[i])f[i] max(f[i], f[j] 1); }int res 0;// 便利所有f[i] for(int i 1; i n; i ) res max(res, f[i]);printf(%d, res);return 0;
}3.最长公共子序列 // 给定两个长度分别为n和m的字符串A和B
// 求即是A的子序列又是B的子序列的字符串的长度最长是多少
#include iostream
#include algorithmusing namespace std;const int N 1010;int n, m;
char a[N], b[N];// 2个字符串
int f[N][N]; int main()
{scanf(%d%d, n, m);scanf(%s%s, a 1, b 1);// 注意1从a[1]开始输入字符串// 从1开始遍历 for(int i 1; i n; i )for(int j 1; j m; j ){f[i][j] max(f[i - 1][j], f[i][j - 1]);if(a[i] b[j]) f[i][j] max(f[i][j], f[i - 1][j - 1] 1);} printf(%d\n, f[n][m]);return 0;
}二、区间dp
1.石子合并 // 设有n堆石子排成一排其编号为1,2,3......n
// 用一个整数描述每堆石子的质量现在要将这n堆石子合并为一堆。// 例子1有1 3 5 2四堆石子我们可以先合并1、2堆代价为4得到4 5 2又合并1、2堆
// 代价为9得到9 2在合并得到11总代价491124
// 例子2先合并1和2、3和4堆代价为47得到4 7再合并代价为11总代价471122
#include iostream
#include algorithmusing namespace std;const int N 310;int n;
int s[N];// 原始数据
int f[N][N];int main()
{scanf(%d, n);for(int i 1; i n; i ) scanf(%d, s[i]);// 前缀和数组 for(int i 1; i n; i ) s[i] s[i - 1];// 按长度从小到大枚举所有状态从2开始 // 区间长度为1不需要代价 for(int len 2; len n; len )// 枚举起点 for(int i 1; i len - 1 n; i ){// 左右端点 int l i, r i len - 1;f[l][r] 1e8;// 要初始化为一个比较大的数 // 枚举分界点 for(int k 1; k r; k )f[l][r] min(f[l][r], f[l][k] f[k 1][r] s[r] - s[l - 1]);}printf(%d\n, f[1][n]);return 0;} 总结
提示这里对文章进行总结
