动态规划基础

动态规划是一种算法思想，关键是理解思想和什么时候用。

算法思想

动态规划用于解决多阶段决策最优化问题，这类问题类似递推。

1.阶段

将问题分为多个阶段，每个阶段之间有联系，即可递推。一般可按问题求解次序或问题的递归性质划分阶段。

2.状态

确定阶段是为了更明确状态，状态是当前阶段的具体内容，即“位置”和当前“位置”的值，做题时可先将状态定义成阶段，发现记录内容不足时，可修改状态定义，或增加状态维度。

3.决策

即当前状态可做出的选择。

4.状态转移方程

确定了状态和决策，即可确定状态转移方程，状态明确要求什么，决策确定如何转移（递推），根据当前状态如何求出写出状态转移方程。

5.边界

边界即递推起点，根据状态转移方程确定。

6.目标解

明确状态定义，即可根据定义确定目标解。

确定以上六点即可解出动规题。

什么时候用动规

动规三要素

1.最优子结构性质

即当前阶段的最优解可由之前阶段的子问题最优解推导出来。能用动规的问题一定有最优子结构性质。

2.重叠子问题

即不同状态存在相同的子问题。

动规通过dp数组记录状态，使得每个子问题只计算一次，大大提高有重叠子问题性质的问题的求解速度，虽不是动规解决的问题的必要性质，但若没有这个性质，动规和别的算法的时间复杂度差不多。

3.无后效性

无后效性是指当前阶段的每个问题的解一旦确定，就不会再被更改。动规解决的问题一定是无后效性的。

可通过判断将可转移的状态间连一条有向边后形成的有向图是否无环来判断是否是无后效性的。

问题符合如上三个要素即可用动规解决。

实现

1.for循环遍历顺序

根据状态转移方程的推导顺序（先求什么，再求什么）确定遍历顺序。

2.空间优化

dp数组只记录可推导出后续问题的问题和结果，其他不做记录。

输入数据若不需复用或存储（有的问题必须存储输入数据，后续算法才能正常进行），则直接用变量接住输入，不开数组。

题目

OpenJudge 9267:核电站

OpenJudge - 9267:核电站

通过求解的先后次序划分阶段，代码如下：

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 50 + 5;
const LL Maxm = 5 + 5;LL dp[Maxn][Maxm];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m;cin >> n >> m;dp[1][1] = 1, dp[1][0] = 1;for (LL i = 2; i <= n; ++i) {dp[i][0] += dp[i - 1][0];for (LL j = 1; j <= min(i, m - 1); ++j) {dp[i][j] += dp[i - 1][j - 1];dp[i][0] += dp[i - 1][j];}}LL res = 0;for (LL j = 0; j <= min(n, m - 1); ++j)  res += dp[n][j];cout << res;return 0;
}

OpenJudge 1759：最长上升子序列

OpenJudge - 1759:最长上升子序列

先将状态定义成阶段，发现不足，在修改。

方法一：增加状态维度

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1000 + 5;LL vct[Maxn], dp[Maxn][2];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n;cin >> n;for (LL i = 1; i <= n; ++i)  cin >> vct[i];for (LL i = 1; i <= n; ++i) {dp[i][0] = 0;dp[i][1] = 1;for (LL j = 1; j < i; ++j) {if (vct[j] < vct[i])  dp[i][1] = max(dp[i][1], dp[j][1] + 1);dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);}}cout << max(dp[n][0], dp[n][1]);return 0;
}

方法二：适当修改状态定义

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1000 + 5;LL vct[Maxn], dp[Maxn];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, res = 0;cin >> n;for (LL i = 1; i <= n; ++i)  cin >> vct[i];for (LL i = 1; i <= n; ++i) {dp[i] = 1;for (LL j = 1; j < i; ++j) {if (vct[j] < vct[i])  dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}cout << res;return 0;
}

OpenJudge 1808：公共子序列

OpenJudge - 1808:公共子序列

状态定义为阶段。

因为是多组数据，注意每个数组的初始化情况。

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 200 + 5;LL dp[Maxn][Maxn];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);string str1, str2;while (cin >> str1 >> str2) {for (LL i = 0; i <= str2.size(); ++i)  dp[0][i] = 0;for (LL i = 1; i <= str1.size(); ++i) {dp[i][0] = 0;for (LL j = 1; j <= str2.size(); ++j) {dp[i][j] = 0;if (str1[i - 1] == str2[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;else  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}cout << dp[str1.size()][str2.size()] << '\n';}return 0;
}

OpenJudge 2989：糖果

OpenJudge - 2989:糖果

明确什么状态能求出当前状态。

注意dp初始化，dp[0][j] = LONG_MIN（不是0，j = 1~(k-1)），dp[0][0] = 0，不然结果是15，会加上无解情况。

最值问题，无解状态设为无限小（大），使得有解状态一定不从无解状态推导出来。

#include <iostream>
#include <climits>#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 100 + 5;
const LL Maxk = 100 + 5;LL dp[Maxn][Maxk - 1];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, k, x;cin >> n >> k;dp[0][0] = 0;for (LL j = 1; j < k; ++j)  dp[0][j] = LONG_MIN;for (LL i = 1; i <= n; ++i) {cin >> x;for (LL j = 0; j < k; ++j)dp[i][j] = max(dp[i - 1][j], dp[i - 1][((j - x) % k + k) % k] + x);}cout << (dp[n][0] <= 0 ? 0 : dp[n][0]);return 0;
}

洛谷 P2066 机器分配

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 10 + 5;
const LL Maxm = 15 + 5;LL vct[Maxn][Maxm], dp[Maxn][Maxm], Res[Maxn][Maxm];void dfs(LL x, LL y) {if (x == 0)  return;dfs(x - 1, y - Res[x][y]);cout << x << ' ' << Res[x][y] << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m;cin >> n >> m;for (LL i = 1; i <= n; ++i) {for (LL j = 1; j <= m; ++j)cin >> vct[i][j];}for (LL i = 1; i <= n; ++i)for (LL j = 1; j <= m; ++j)for (LL k = 0; k <= j; ++k) {if (dp[i][j] <= dp[i - 1][j - k] + vct[i][k]) {dp[i][j] = dp[i - 1][j - k] + vct[i][k];Res[i][j] = k;}}cout << dp[n][m] << '\n';dfs(n, m);return 0;
}