动态规划思想
就是切割问题变成一堆小问题,最好子问题之间可以递推,这样就能利用之前的子问题的答案得出新的结果。
可以削减总量,比如求n个数的什么什么,可以削n的大小,n削到n-1……一直到1,1的结果很好求,然后利用1的结果求2,然后再一直求到n。
也可以不削总量削单量,比如上面的把要求的结果切割成多个n个数的小结果叠加,求n个数的小结果a,b……。最后再把a,b……加起来得最终结果
核心的核心是分解子问题,怎么分解没有定式,重点是如何递推,如何设置条件
基本流程:
- 定义状态:确定问题中的关键状态,这些状态描述了问题的特征。
- 确定状态转移方程:找到状态之间的递推关系,即如何通过已知的状态求解未知的状态。
- 初始化:将问题的初始状态设定为已知的值。
- 自底向上求解:按照状态转移方程从初始状态开始逐步求解,直到达到最终状态。
- 根据最终状态得到结果:得到最终状态的值,即为原问题的解。
背包问题
给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内(背包限定重量),选择出价值最高的方案。
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
整数划分
这个可以当作一个变相的完全背包问题,容量为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
状态压缩的意思就是将多个状态压缩成二进制数表示,比如下面的就是把每一列的状态压缩成一个二进制数了,可以节省空间。
蒙德里安的梦想
这个问题就相当于在棋盘摆长方形,当我们的所有横向的长方形放完了,剩下的就只能按照放纵向的小方格,所以横着摆放的方案就是所有的方案。
我们用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
在子树和根节点上作文章
没有上司的舞会
就相当于一棵树,父节点和子节点不能同时出现。
我们用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的过程,优点是代码思路比较好写,而且在一些不容易递推的关系好写。
像下面的滑雪问题,如果顺序遍历的话就难以递推。这个就会是用什么推什么,同时把用过的都记下来,下次再用就不用推了。
滑雪
文章来源:https://www.toymoban.com/news/detail-852036.html
用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模板网!