
动态规划
动态规划算法把原算法视作若干个重叠子问题的逐层递进,每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算之后,动态规划才会执行下一个阶段的计算。
为了保证这些计算能够按顺序、不重复地进行,动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也叫“无后效性”。换言之,动态规划对状态空间的遍历构成一张有向无环图,遍历顺序就是该有向无环图的一个拓扑序。有序无环图中的节点对应问题中的“状态”,图中的边则是对应状态之间的“转移”,转移的选取就是动态规划中的“决策”。
在很多情况下,动态规划用于求解最优化问题。此时,下一阶段的最优解应该能够由前前面各阶段的子问题的最优解求出。这个条件被称为“最优子结构性质”。
“状态”、“阶段”和“决策”是构成动态规划算法的三要素,而“子问题重叠性”,“无后效性”和“最优子结构性”是问题能用动态规划求解的三个基本条件。
动态规划算法把相同的计算过程作用于各阶段的同类子问题,就好像把一个固定的公式套在格式相投的若干输入数据上运行。因此,我们一般只需要定义出DP的计算过程,就可以编程实现了,这个计算过程就称为“状态转移方程”。
闫式思考法
从集合的角度来思考问题:?

例题:AcWing 1015. 摘花生


集合含义:所有从? ?走到? ?的所有路线的最大值?
在状态计算中,很重要的划分依据:“最后”
集合的划分依据:1.不重 2.不漏(在不重复这一点是,可以出现重复算,因为最后是取子集的最最值)


AC代码?
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int w[N][N];
int f[N][N];
int main()
{
int T; cin >> T;
while(T -- )
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j];
cout << f[n][m] << endl;
}
return 0;
}
例题:AcWing 1018. 最低通行费?


跟上面的摘花生的是类似的题目类型。多了时间上面的限制(? ?)。
这个时间上面的限制 等价于 不走回头路
由于所求的是最小值,这道题在求解的时候需要对边界进行初始化。
AC代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n;
int w[N][N];
int f[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
scanf("%d", &w[i][j]);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
if(i == 1 && j == 1) f[i][j] = w[i][j];
else
{
f[i][j] = INF;
if(i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
}
cout << f[n][n] << endl;
return 0;
}
例题:AcWing 1027. 方格取数

输入样例:
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例:
67
这一题相比于前面两题,多了总共走两次这样的限制条件。?
在只走一次的情况中:
?表示的是?所有从? ?走到? ?的所有路线的最大值?
![\small f[i,j]=max(f[i - 1][j],f[i][j-1]) +w[i][j]](https://latex.codecogs.com/gif.latex?%5Csmall%20f%5Bi%2Cj%5D%3Dmax%28f%5Bi%20-%201%5D%5Bj%5D%2Cf%5Bi%5D%5Bj-1%5D%29%20+w%5Bi%5D%5Bj%5D)
走两次的情况中:
?表示所有从? , ?走到? ?的路径的所有集合的最大值
如何处理“同一个格子不能被重复选择”?
只有在? ?时,两条路径的格子才会重合?
??表示两个人同时走 k 步(横纵坐标之和)(类比摘花生)
?表示所有从?? ,? ?分别走到? ?的路径的最大值
 
AC代码?
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n;
int a, b, c;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for(int k = 2; k <= n + n; k ++ )
for(int i1 = 1; i1 <= n; i1 ++ )
for(int i2 = 1; i2 <= n; i2 ++ )
{
int j1 = k - i1, j2 = k - i2;
if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
{
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
cout << f[n + n][n][n];
return 0;
}
|