C++算法之动态规划(ACWING题目）-Toy模板网

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

动态规划时间复杂度：状态数量*转移计算量

线性DP

一.数字三角形

动态规划：
1.状态表示：
集合：f[i, j]表示所有从起点走到(i, j)的路径
属性：所有路径上的数字之和的最大值
2.状态计算：
如何得到f[i, j]?
从左边路径走到和从右边路径走到
从左边路径走到该点：f[i - 1, j - 1] + a[i, j]
从右边路径走到该点：f[i - 1, j] + a[i, j];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= n; j ++)
f[i][j] = -INF;
赋初值的时候由于状态转移方程中会使用f[i - 1]，为了避免f[-1]非法数据，三角形存储在1-n中
考虑状态转移的时候由于会有负数，因此对于非法点也需要赋初值-INF，从0-n

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]);

二.最长上升子序列
1.状态表示
集合：所有以i结尾的上升子序列的长度
属性：集合的最大值即f[i]的最大值
2.状态计算：
以i结尾，倒数第二个数从1到i - 1的数字的集合中的最大值

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); //如果满足严格单增就加1
}
最后答案为f[1]-f[n]中的最大的数

输出最长上升子序列：
for(int i = 1; i <= n; i ++)
{
f[i] = 1;
g[i] = 0;
for(int j = 1; j < i; j ++)
if(a[j] < a[i])
if(f[i] < f[j] + 1)
{
f[i] = f[j] + 1;
g[i] = j;
}
}
g数组的作用：记录以i结尾的最长数组的倒数第二个数，即从哪个元素加上最后一个i得到最长的上升子序列

for(int i = 0, len = f[k]; i < len; i ++)
{
cout << a[k];
k = g[k];
}
通过从后往前查找g数组将1-n中以k结尾的最长数组进行还原。

最长上升子序列优化：
如数组：3 1 2 1 8 5 6
第三个开始的元素，若子序列可以接在3后面则一定可以接在1后面，因此3不用存下来
对于每一种长度的子序列，选择结尾最小的进行存储一定是最优解
对于不同长度的子序列，最小的结尾一定随着长度的增加而增加
对于a[i]，只需要从前面找到长度最大且结尾小于a[i]的元素，由于结尾保持单增因此用二分查找找到小于a[i]的元素
int a[N]; //a数组存储的是数组
int q[N]; //q数组存储的是以i结尾的最长的子序列的结尾的值(q单增)
for(int i = 0; i < n; i ++)
{
int l = 0, r = len;
while(l < r) //二分
{
int mid = l + r + 1>> 1; //二分中取的是l=mid，因此要+1
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1); //当前最大长度为本身(不加入a[i])或者加入a[i]
q[r + 1] = a[i];
}

三.最长公共子序列
划分依据：a[i]和b[j]
1.状态表示f[i, j]
集合：所有由第一个序列的前i个字母，和第二个序列的前j个字母构成的子序列
属性：MAX
2.状态计算:
00：都不选 01：选b不选a 10：选a不选b 11：选a选b
00：f[i - 1, j - 1]
11:f[i - 1, j - 1] + 1
**********
01：不能用f[i - 1, j]表示,f[i - 1, j]表示的是第一个串中前i-1和第二个串中前j的最长公共子序列
而01表示的是不选第一个串中的第i位，要选第二个串中的第j位的情况。f[i - 1, j]一定包含01这种情况
当我们用f[i - 1, j]表示01这种情况的时候会考虑重复，但是不影响最终的结果

**********
f[i - 1, j - 1]包含在f[i - 1, j]和f[i, j - 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]); //先取f[i][j - 1]和f[i - 1][j]中的最大值
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); //当相等的时候选择取或者不取
}




四.最短编辑距离
for(int i = 0; i <= m; i ++) f[0][i] = i;
for(int i = 0; i <= n; i ++) f[i][0] = i; //初始化
初始化操作中对当其中一个数组长度为0的情况分别进行初始化，需要操作的数目为i的值

for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
f[i][j]有三种可能，增加，删除和修改。
f[i][j]为增加或者删除中的最小操作数目。
当第i个元素相同则不需要进行操作，若不同则将f[i - 1][j - 1]的操作数目加一
当第i个元素相等的时候f[i][j] = min(f[i][j], f[i - 1][j - 1]);可以改为f[i][j] = f[i - 1][j - 1];
易知f[i][j]一定是严格大于f[i - 1][j - 1]的

五.编辑距离
给定 n 个长度不超过 10 的字符串存储方法：
const int N = 15, M = 1010;
int n, m; //n总共字符串个数，m为询问个数
int f[N][N];
char str[M][N]; //str二维数组存储n个长度不超过10的字符串

scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%s", str[i] + 1); //由于动态规划要使用f[i - 1]，因此从1开始存

char s[N]; //s为char类型的数组
main主函数中的函数引用：edit_distance(str[i], s)
函数的写法：
int edit_distance(char a[], char b[])

六.整数划分
方法一：转化成背包问题
容量为n的一个背包，有物品体积为1-n，每种物品可以使用无限次，完全背包问题
///? f[i][j] = f[i - 1][j] + f[i][j - i] ?///
f[i - 1][j] 表示不选第i个物品，体积为j的情况
f[i][j - i]表示从1~i中选，总体积为j - i的情况
1. f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - i * 2] +...+ f[i - 1][j - i * s]
2. f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - i * 2] +...+ f[i - 1][j - i * s]
观察可知1,2两式可合并为f[i][j] = f[i - 1][j] + f[i][j - i]，证毕
可以化简为一维等式：f[j] = f[j] + f[j - i];
对于f[j]，右边的f[j]是还没有更新的，对应的是i-1的情况，由于从小到大枚举，因此f[j-i]已经更新过了
对应的是i的情况

for(int i = 1; i <= n; i ++)
for(int j = i; j <= n; j ++)
f[j] = (f[j] + f[j - i]) % M;
cout << f[n] << endl;

方法二：
集合：
所有总和是i，并且恰好表示成j个数的和的方案

属性：
数量

状态计算：
1.j个数中的最小值是1 去掉一个1就可以变成f[i - 1, j - 1]
2.j个数中最小值大于1 都减去1后变成f[i - j, j]
f[i, j] = f[i - 1, j - 1] + f[i - j, j]
ans = f[n,1]+f[n,2]+...+f[n,n];


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

int res = 0;
for(int i = 1; i <= n; i ++) res = (res + f[n][i]) % mod;

区间DP

一.石子合并
状态表示(f[i, j]从i到j石子的区间)
集合：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式
属性：min(所有合并方式中的代价的最小值)
状态计算：用最后一次合并的分界线位置进行分类
如从i到j，用k划分，f[i, k] + f[k + 1, j] + s[j] - s[i - 1] //s是前缀和
for(int len = 2; len <= n; len ++) //len表示合并的区间的长度(f[i][j]中i到j的长度)
for(int i = 1; i + len - 1 <= n; i ++) //i表示左端点
{
int l = i, r = i + len - 1; //l和r表示区间的左端点和右端点
f[l][r] = 0x3f3f3f3f;
for(int k = l; k <= r; k ++) //需要包含两边的端点
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}

状态压缩DP

状态看成二进制数，0和1看成不同的情况

1.蒙德里安的梦想
二维数组f[][]第一维存储列数，表示第n列，第二维存储状态，有k行则有2^k种状态，用十进制数表示为0~2^k-1
状态划分的依据为上一列是否有一个横着的1*2的矩形伸到了这一列
f[][]总体表示第n列的方案的数目

for(int i = 0; i < 1 << n; i ++)
{
st[i] = true;
int cnt = 0; //当前这一段连续0的个数
for(int j = 0; j < n; j ++)
if(i >> j & 1) //如果当前这一位是1
{
if(cnt & 1) st[i] = false; //判断上一段的0的个数
cnt = 0;
}
else cnt ++;
if(cnt & 1) st[i] = false;
}

f[0][0] = 1; //由于第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];




2.最短Hamilton路径
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
状态表示：f[i][j]
i看成一个二进制数，表示点是否走过了
集合：所有从0走到j，走过的所有点是i的所有路径
属性：min
状态计算：

for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
cin >> w[i][j]; //读入边

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) //如果从0走到j，i里面必须包含j
for(int k = 0; k < n; k ++)
if((i - (1 << j)) >> k & 1) //如果是从k点转移过来的，那么i除去j点后一定包含k这个点
//i - (1 << j)表示i除去j这个点
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl; //走完了所有的点，i的每一位都是1，最后走到的点是n-1

树形DP

1.没有上司的舞会

状态表示：f[u,1/0]
集合：所有从以u为根的子树中选择，并且选/不选u这个点的方案
属性：max
状态计算
f[u, 0]=子节点选或者不选中的最大值
f[u, 1]=子节点不选的最大值
树用邻接表存储
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N]; //判断是否有父节点

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

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];
   }
}

main主函数中：
连接边
for(int i = 0; i < n - 1; i ++)
{
   int a, b;
   cin >> a >> b;
   has_father[a] = true; //a为b的父节点，将has_father[a]改为true
   add(b, a);
}
找根节点
int root = 1;
while(has_father[root]) root ++; //找根节点

记忆化搜索

1.滑雪

f[x][y]以(x, y)为起点的能够到达的最远的距离

int dp(int x, int y) {
   if (f[x][y] != -1) //需在主函数中将f全部置为-1
       return f[x][y];
f[x][y] = 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])
           f[x][y] = max(f[x][y], dp(a, b) + 1); //更新f[x][y]
   }

return f[x][y];
}

文章来源地址https://www.toymoban.com/news/detail-829657.html

到了这里，关于C++算法之动态规划(ACWING题目）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！