算法笔记14.动态规划

这篇具有很好参考价值的文章主要介绍了算法笔记14.动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划思想

就是切割问题变成一堆小问题,最好子问题之间可以递推,这样就能利用之前的子问题的答案得出新的结果。

可以削减总量,比如求n个数的什么什么,可以削n的大小,n削到n-1……一直到1,1的结果很好求,然后利用1的结果求2,然后再一直求到n。

也可以不削总量削单量,比如上面的把要求的结果切割成多个n个数的小结果叠加,求n个数的小结果a,b……。最后再把a,b……加起来得最终结果

核心的核心是分解子问题,怎么分解没有定式,重点是如何递推,如何设置条件

基本流程:

  1. 定义状态:确定问题中的关键状态,这些状态描述了问题的特征。
  2. 确定状态转移方程:找到状态之间的递推关系,即如何通过已知的状态求解未知的状态。
  3. 初始化:将问题的初始状态设定为已知的值。
  4. 自底向上求解:按照状态转移方程从初始状态开始逐步求解,直到达到最终状态。
  5. 根据最终状态得到结果:得到最终状态的值,即为原问题的解。

背包问题

给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内(背包限定重量),选择出价值最高的方案。

01背包问题

最简单的背包问题,限定每种物品只有一个,拿的结果不是0就是1。

我们用两个限制条件,物品最大个数和最大重量。

我们划分集合为两个部分,以上一层为基础的话,这一层的变化就是多了一件物品(物品最大个数加1)。那么就可以分为两种情况,拿这件物品和不拿这件物品,然后我们在满足条件的情况下从两个方案里面挑一个最大的。

const int N = 1010;

int n, m;
int v[N], w[N]; //v代表体积,w代表价值
int f[N][N]; //第一个代表物品个数,第二个代表重量,存的值是价值

int main()
{
	for(int i = 1; i <=n; i++)
		for (int j = 0; j <= m; j++)
		{
			f[i][j] = f[i - 1][j];
			//如果限制的上限j大于最后一件物品的话,那就可以在两个方案中选一个
			if (j >= v[i])
				f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
}

我们可以用一维数组来优化这个问题,只要注意一下第二重循环用逆序就可以了。

const int N = 1010;

int n, m;
int v[N], w[N]; //v代表体积,w代表价值
int f[N];  //背包容量为 j 时的最大总价值

int main()
{
	for (int i = 1; i <= n; i++)  //遍历每个物品
		for (int j = m; j >= v[i]; j--)  //遍历背包容量(上限是m,所以从m开始--)
			//注意我们需要逆序列遍历,是因为j - v[i],这个值肯定是比当前的j小的
			//如果我们正序遍历的话,j - v[i]这个值(注意这里只是单纯的一个比j小的值)
			//就会在前面被考虑,那就有可能已经放入i这个物品了,会导致重复
			f[j] = max(f[j], f[j - v[i]] + w[i]);
}

完全背包问题

完全背包问题就是不再限制物品的个数了,可以取无限个。

我们还是按照取物品的个数来划分集合,之前是0个和1个两种情况,现在我们可以划分多个集合,直到容量不够。

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	for (int i = 1; i <= n; i++)  //遍历每个物品
		for (int j = 0; j <= m; j++)  //遍历背包容量
			for (int k = 0; k * v[i] <= j; k++) //取k个物品i
				f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}

我们这个问题也可以优化,

f[i , j ] = max( f[i-1,j] , f[i- 1,j - v[i]+ w[i] ,  f[i - 1,j-2 * v[i]]+2 * w[i] , f[i -1,j - 3 * v[i]]+3 * w[i] , .....)
f[i , j - v[i]]= max(       f[i - 1,j - v[i]] ,        f[i - 1,j - 2 * v[i]] + w[i] ,   f[i - 1,j- 3 * v[i]]+2 * w[i] , .....)

可以得出f[i][j]=max(f[i, j - v[i] ] + w[i] , f[i - 1][j]) 

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	for (int i = 1; i <= n; i++)  //遍历每个物品
		for (int j = 0; j <= m; j++)  //遍历背包容量
		{
			f[i][j] = f[i - 1][j];
			if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		}
}

我们还可以继续在这个基础上优化成一维数组,跟01背包的很像

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
	for (int i = 1; i <= n; i++)  //遍历每个物品
		for (int j = v[i]; j <= m; j++)  //遍历背包容量
			f[i] = max(f[j], f[j - v[i]] + w[i]);
}

多重背包问题

这个的区别每件物品有自己的数量了,不是无限个了。

还是以取的物品的个数来划分集合

const int N = 110;

int n, m;
int v[N], w[N],s[N];
int f[N][N];

int main()
{
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= m; j++)
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
				f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}

我们不能用完全背包的优化思路来优化,因为最后会多出来一个(多重背包问题的物品个数是固定的,所以不能对齐)

我们可以用一个数学规律来拼凑,假设我们有200个物品,我们将它分成好几组,然后用这些组来取。

原理是1,2,4,8……这些数字,可以拼凑出从0到总和的我们想要的任意一个数。比如说我们只取1,2,4。它们的和是7,我们就可以用这三个数拼出1到7的任意一个数,比如5就是1+4,6就是2+4。

(当然每个数只能用一次)

200个物品我们要分成的组就是1,2,4,8,16,32,64,73。最后一个数不能取128,否则会超200,200减1到64就是73。1到64我们就可以拼出0到127之间的任意一个数,再加上73,我们就能拼出0到200之间的任意一个数了,两个范围相交,我们就能拼出0到200之间的任意一个数了。

 然后我们将所有的物品都分好组,每组物品都当一个新物品看,就能直接当成01背包问题做了。

const int N = 25000, M = 25000;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b, s;
		cin >> a >> b >> s;
		int k = 1;
		while (k <= s)
		{
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if (s > 0)
		{
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}

	n = cnt;

	for (int i = 1; i <= n; i++)
		for (int j = m; j >= v[i]; j--)
			f[i] = max(f[j], f[j - v[i]] + w[i]);
}

 分组背包问题

这个是我们有n组物品,每组物品只能从中选一个。

我们提出的状态就是前i组物品中选,并且总体积不大于j

我们通过选第i组物品的哪个来划分集合,不选,选第1个……

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 0; j--)
			for (int k = 0; k < s[i]; k++)
				if (v[i][k] <= j)
					f[j] = max(f[j], f[j - v[i][k]] + w[i]);
}

线性DP

线性DP就是递推方程有一个明显的递进关系,可以是一维的也可以是二维的

数字三角形

给定一个由n行数字组成的数字三角形,计算从三角形的顶至底的一条路径,使该路径经过的数字总和最大(每次只能向下走)。

用一个二维数组存储,第一维表示从右上向左下的第n列,第二维表示从这列上往下数第n个数。存储的是从起点开始走到这个点的路径的最大值。

然后将集合划分为来自左上和来自右上,就是从f[i-1, j-1] + a[i,j]和f[i-1,j] + a[i,j]里面选最大值

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
	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]);
}

最长上升子序列

给定一个数列,求数值严格单调递增的子序列的长度是多少(元素可以不连续)

我们用一维就可以表示,存储以i结尾的最长子序列的最大值。

以子序列包不包含前面的数来划分集合,f[i] = max(f[j] + 1), j = 0,1……i-1。

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
	for (int i = 1; i <= n; i++)
	{
		f[i] = 1; //只有a[i]一个数的情况
		for (int j = 1; j < i; j++)
		{
			if (a[j] < a[i])
				f[i] = max(f[i], f[j] + 1);
		}
	}
}

最长公共子序列

给定两个长度分别为N和M的字符串A和B,求最长的公共子序列。

用二维数组表示,第一维表示第一个序列的前i个字母,第二维表示第二个序列的前j个字母,值表示最长公共子序列

我们以a[i],b[j]是否出现在子序列中来划分集合,这样可以划分出四个集合。

这四个集合中都不出现和都出现比较容易表示,一个是f[i-1][j-1],一个是f[i-1][j-1]+1。如果是一个出现一个不出现,不能用f[i-1][j]表示,因为这个只能保证不包含a[i]和可能有b[j]。

不过其实用这个也没有影响,只是有些重叠,但是我们是求最大值,所以有重叠也可以。正因为有重叠,我们可以省略f[i-1][j-1],因为已经被包含了

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
	for(int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			f[i][j] = max(f[i - 1][j], g[i][j - 1]);
			if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
}

 1

区间DP

区间DP比线性DP更加复杂,主要是在区间上处理问题,所以情况会比线性更多.可能需要再开循环来遍历所有的区间划分情况.

石子合并

有N堆石子,现要将石子合并成一堆,每次只能合并相邻的2堆石子,合并花费为新合成的一堆石子的数量。求将这N堆石子合并并代价最小

我们用一个二维数组f[i][j]来存储,表示所有从第i堆石子到第j堆石子合并的最小的代价,我们以最后一次合并的分界线来划分集合,就是假如有n堆,我们最后得到是前m堆合并的一个大堆和剩下的合并的一个大堆,最后合并成一个堆,我们的分界线就是这两个大堆的分界线.

然后我们就可以得到很多分界方式,我们再在这里面选最小的.

#include <iostream>

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
	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]);
	    }
}

计数类DP

整数划分

算法笔记14.动态规划,动态规划,算法

这个可以当作一个变相的完全背包问题,容量为n,有从1到n物品,每种选择方式就是一种划分方法(因为选择方式不看排序,只看元素,可以当作排好序的)

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
	f[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			f[j] = (f[j] + f[i - j]) % mod;
}

数位统计DP

计数问题

给定两个整数a和b,求a和b之间的所有数字中0~9的出现次数。

最重要的一步是分情况讨论,我们首先实现一个count函数(传入n和x,返回1~n中x出现的次数)

然后用count(b, x) - count(a - 1, x)就可以得到a到b中x出现的次数。

再然后,我们实现count函数,count函数还可以再细分,我们将x在每一位出现的次数加起来,就可以得到count的结果

假设说我们有一个数abcdefg,我们要分别求1在第4位出现的次数

1 <= xxx1yyy <= abcdefg,可以分为两种情况

第一种是xxx = 000~abc - 1,yyy = 000~999(这样的话次数就是abc * 1000)

第二种是xxx = abc,这个又可以根据数的d的取值分三种情况。

(1)d < 1,abc1yyy > abc0efg(次数为0)

(2)d = 1,yyy = 000~efg(次数为efg + 1)

(3)d > 1,yyy = 000~999(次数为1000)

我们将所有数的所有的情况结合起来就能得到最终答案。

状态压缩DP

状态压缩的意思就是将多个状态压缩成二进制数表示,比如下面的就是把每一列的状态压缩成一个二进制数了,可以节省空间。

蒙德里安的梦想

算法笔记14.动态规划,动态规划,算法

这个问题就相当于在棋盘摆长方形,当我们的所有横向的长方形放完了,剩下的就只能按照放纵向的小方格,所以横着摆放的方案就是所有的方案。

我们用f[i][j]来表示状态(存储的是达到这个状态的方案数),表示我现在要摆第i列,但是存储的不是第i列的值,而是上一列的摆放结果对第i列的影响。

因为一个横向的长方形会占据两列,假设i-1列放了一个,那么第i列的方格相当于被占据了

我们用01表示这个方格有没有被上一列的长方形占据,有几行就用几位二进制,再转化为十进制作为j

然后我们给第i列填方块的时候,需要参考第i-1列(用到f[i-1][k]和f[i][j])

我们填方块还需要满足两个条件,不能重叠,剩余的连续的空块必须是偶数(不是偶数就不能填入纵向长方形了)。我们可以利用位运算计算。

k & j == 0可以保证不重叠。

j | k 可以得到第i-1列当中的方块填充情况,因为j表示的是从第i-1列伸出来的,k只表示i-2列的,需要合并,那么这个j | k 的值中的连续0必须是偶数。

const int N = 12, M = 1 << N;

int n, m;
int f[N][M];
bool st[M];  //存储状态是否合法

int main()
{
	int n, m;
	while (std::cin >> n >> m, n||m)
	{
		memset(f, 0, sizeof f);

		for (int i = 0; i < 1 << n; i++) //i小于2的n次方
		{
			st[i] = true;
			int cnt = 0;
			for (int j = 0; j < n; j++)
			{
				if (i >> j & 1)
				{
					if (cnt && 1) st[i] = false;
					cnt = 0;
				}
			}
			if (cnt && 1) st[i] = false;
		}

		f[0][0] = 1;
		for (int i = 1; i <= m; i++)
			for (int j = 0; j < 1 << n; j++)
				for (int k = 0; k < 1 << n; k++)
					if ((j & k) == 0 && st[j | k])
						f[i][j] += f[i - 1][k];
	}
}

最短Hamilton路径

给定一张n个点的带权无向图,点从0至n-1标号,求起点0到终点的不重不漏的经历所有点的最短路径。

这个我们用f[i][j]表示状态,i用二进制表示所有的点有没有被走过,j表示路径结束目标点。存储的是最短路径。

然后我们通过路径的倒数第二个点,也就是终点的前一个点是哪个点来划分状态。

#include <iostream>

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (i >> j & 1)
				for (int k = 0; k < n; k++)
					if ((i - (1 << j)) >> k & 1)
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}

树形DP

在子树和根节点上作文章

没有上司的舞会

算法笔记14.动态规划,动态规划,算法

就相当于一棵树,父节点和子节点不能同时出现。

我们用f[u][0]和f[u][1]来表示状态,第一个表示所有以u为根的子树中选择,并且不包含u这个点。第二个表示所有以u为根的子树中选择,并且包含u这个点。

const int N = 6010;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool hasFather[N];

void dfs(int u)
{
	f[u][1] = happy[u];

	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		dfs(j);

		f[u][0] += max(f[j][0], f[j][1]);
		f[u][1] += f[j][0];
	}
}



int main()
{
	int root = 1;
	while (hasFather[root]) root++;
	dfs(root);
}

记忆化搜索

记忆化搜索说白了就是利用递归实现DP的过程,优点是代码思路比较好写,而且在一些不容易递推的关系好写。

像下面的滑雪问题,如果顺序遍历的话就难以递推。这个就会是用什么推什么,同时把用过的都记下来,下次再用就不用推了。

滑雪

算法笔记14.动态规划,动态规划,算法

用f[i][j]表示状态,表示所有从(i,j)开始滑的路径的最大值。用上下左右四个方向划分集合。文章来源地址https://www.toymoban.com/news/detail-852036.html

const int N = 310;

int n, m;
int h[N][N];
int f[N][N];

int dx[4] = { -1, 0, 1, 0 }, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
	int& v = f[x][y];
	if (v != -1) return v;
	v = 1;
	for (int i = 0; i < 4; i++)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
			v = max(v, dp(a, b) + 1);
	}
	return v;
}

int main()
{
	memset(f, -1, sizeof f);
	int res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			res = max(res, dp(i, j));
}

到了这里,关于算法笔记14.动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法笔记(Java)——动态规划

    动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的, 动规和递归的区别是动规不是暴力的

    2024年02月08日
    浏览(49)
  • 算法学习笔记(动态规划——01背包)

    先来聊聊动态规划,动态规划是分治法的一种体现,把一个问题分解成若干个子集,通过当前状态,经过操作得到下一个状态,最后得到最优问题解的一种方法。 步骤: 设定状态,保存状态 根据状态设定转移方程 确定边界 其中的01背包解决的是关于选择的动态规划问题,

    2024年03月25日
    浏览(54)
  • 动态规划算法刷题笔记【状压dp】

    a1 == 1 判断是否为奇数,如果为1,则为奇数 因为奇数二进制末位一定是1,所以 与1 得到的结果是1 这里,114——2 14 ——第15位是1,可以表示14个1 i(1j)—— 从0开始是因为,原本第1位就是1。所以j=0时,对应的就是 i 的最低位 F l o y d Floyd Fl oy d 算法: n o w ∣ f l a g = = f l

    2024年02月11日
    浏览(43)
  • Acwing-基础算法课笔记之动态规划(背包问题)

    01背包中的0和1指的是放与不放,而且不能出现放多个的情况,背包只能放相同物品中的一个; 首先是对 d [ i ] [ j ] d[i][j] d [ i ] [ j ] 数组的解释,该数组表示的是只看前 i i i 个物品,总体积是 j j j 的情况下,总价值最大是多少; 不选第 i i i 个物品,只考虑前 i − 1 i-1 i −

    2024年04月17日
    浏览(50)
  • 算法基础复盘笔记Day09【动态规划】—— 背包问题

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月22日
    浏览(51)
  • 算法基础复盘笔记Day10【动态规划】—— 线性DP

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月21日
    浏览(83)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(56)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(42)
  • Day46- 动态规划part14

    题目一:1143. 最长公共子序列 1143. 最长公共子序列 给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的

    2024年02月21日
    浏览(40)
  • 数据结构与算法之美学习笔记:42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?

    本节课程思维导图: 利用 Trie 树,可以实现搜索引擎的提示功能,这样可以节省用户输入搜索的时间。实际上,搜索引擎在用户体验方面的优化还有很多,比如你可能经常会用的拼写纠错功能。 当你在搜索框中,一不小心输错单词时,搜索引擎会非常智能地检

    2024年02月03日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包