【算法】动态规划之DP问题（5.10更新完）

前言：

本系列是看的B站董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

树塔-记忆化搜索

特点（前提）：从上向下的累加和是不能重复使用的，从下向上的累加和是可以重复使用的

把题目变成二叉树的形式：4的左子树分别是下一行的8和下一行右边的3，依次类推，每一个树的左子树都是他的下一行的数和下一行数的右边的那个数

int a[9][9] =
{   {1},
	{4,6},
	{8,3,9},
	{5,7,2,1}};
     int n = 4;
    int f[9][9];//记录从上向下的累加和
	int dfs(int x, int y)
	{
		if (f[x][y] != 0) return f[x][y];//说明该点已经遍历过
		if (x == n - 1) f[x][y] = a[x][y];//说明已经全部遍历完了
		else
		f[x][y] = a[x][y] + max(dfs(x + 1, y), dfs(x + 1, y + 1));
		return f[x][y];
	}

线性DP

数塔

int calu(int x, int y)
{
	int x,  y;
	for (x = n - 2; x >= 0; x--)
		for (y = 0; y <= x; y++)//这样就可以弄成塔的形式
			a[x][y] += max(a[x + 1][y], a[x + 1][y + 1]);
	cout << "max=" << a[x][y];
}

如果需要输出路径的话，需要有一个前驱路径数组p[x][y]和一个备份数组b[x][y];

前驱路径数组主要是记录y的增值的，把两种情况（a[x + 1][y]>/<=a[x + 1][y + 1]）分别设为0和1,r然后在通过遍历数组b[x][y],y=y+p[x][y]进行输出

最长上升子序列

动态规划（O（n²））


    for (int i = 1; i <= n; i++) f[i] = 1;//把初始化化长度都设为1
    for (int i = 2; i <= n; i++)
   {
    for (int j = 1; j < i; j++)
    if (a[i] > a[j]) f[i] = max(f[j] + 1,f[i]);//分别依次计算不同下标时候的长度
    for (int i = 1; i <= n; i++) ans = max(ans, f[i]);//遍历寻找长度最长的长度
   }