动态规划入门
动态规划是编程解题的一种重要手段。1951年美国数学家R.Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优化原理”，从而创建了解决最优化问题的一种新方法：动态规划。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
动态规划的基本概念：
-
阶段：把所给问题的求解过程恰当地分成若干个相互联系的阶段，以便于求解。过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量，常用 $k$ 表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程。
-
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。通常一个阶段有若干个状态，状态通常可以用一个或一组数来描述，称为状态变量。
-
决策：表示当过程处于某一阶段的某个状态时，可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。不同的决策对应着不同的数值，描述决策的变量称决策变量。
-
状态转移方程：动态规划中本阶段的状态往往是上一阶段的状态和上一阶段的决策的结果，由第 $i$ 段的状态 $f(i)$,和决策 $u(i)$ 来确定第 $i+1$ 段的状态。状态转移表示为 $F(i+1) = T(f(i),u(i))$ ，称为状态转移方程。
-
策略：各个阶段决策确定后，整个问题的决策序列就构成了一个策略，对每个实际问题，可供选择的策略有一定范围，称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。
动态规划必须满足最优化原理与无后效性。
-
最优化原理：“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。也就是说一个最优策略的子策略，也是最优的。
-
无后效性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各个状态的影响。
蒜头君回家
蒜头君要回家，已知蒜头君在 $(1,1)$ 位置，家在 $(n,n)$ 坐标处。蒜头君走到一个点 $(i,j)$ 会花费一定的体力 $a_{ij}$，而且蒜头君只会往家的方向走，也就是只能往上，或者往右走。蒜头君想知道他回到家需要花费的最少体力是多少。
例如下图所示，格子中的数字代表走到该格子花费的体力：
对于该图来说，最优策略已在图上标出，共花费体力为：$3+2+4+3=12$。
我们把走到一个点看做一个状态，蒜头君想，我走到一个点只有两种方式，一个是从下面走到该点，一种是从左边走到该点。那么点 $(i,j)$ 要么是从 $(i-1,j)$ 走到 $(i,j)$，要么是从点 $(i,j-1)$ 走到 $(i,j)$。
所以从哪个点走到 $(i,j)$ 就是一个决策，我们用 $dp(i,j)$ 来代表走到点 $(i,j)$ 一共花费的最少体力。
我们需要花费最少力气走到家，所以可以得到状态转移方程： $dp(i,j) = min(dp(i-1,j), dp(i,j-1)) + a_{ij}$ 。根据转移方程我们可以推出走到每个点花费的最少体力。
对于图中的边界点，要在转移前加上判断是否为边界，如：点 $(1,3)$ 只能从点 $(1,2)$ 走过来，点 $(3,1)$ 只能从点 $(2,1)$ 走过来。
动态规划的题目的核心是写出状态转移方程，对于一个动态规划的题目，如果我们能写出转移方程那么代码实现就变得简单多了。大部分的动态规划题目，在计算出转移方程后，可以用类似于递推的循环嵌套，来写出代码。
主要代码：
1int a[100][100]; // a数组代表走到点(i,j)花费的体力
2int dp[100][100]; // dp数组代表走到点(i,j)一共花费的最少体力
3dp[1][1] = 0;
4for (int i = 1; i <= n; ++i)
5{
6 for (int j = 1; j <= n; ++j)
7 {
8 if (i == 1 && j == 1)
9 {
10 continue;
11 }
12 else if (i == 1)
13 { //边界点
14 dp[i][j] = dp[i][j - 1] + a[i][j];
15 }
16 else if (j == 1)
17 { //边界点
18 dp[i][j] = dp[i - 1][j] + a[i][j];
19 }
20 else
21 {
22 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j]; //转移方程
23 }
24 }
25}
过河
在一个夜黑风高的晚上，有 $n$ 个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不超过两人通过，他们只有一个手电筒，所以每次过桥后，需要有人把手电筒带回来，第 $i$ 号小朋友过桥的时间为 $a[i]$ ，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
我们先将所有人按花费时间递增进行排序，假设前 $i$ 个人过河花费的最少时间为 $opt[i]$，那么考虑前 $i-1$ 个人已经过河的情况，即河这边还有1个人，河那边有 $i-1$ 个人，并且这时候手电筒肯定在对岸，所以 $opt[i] = opt[i-1] + a[1] + a[i]$ (让花费时间最少的人把手电筒送过来，然后和第 $i$ 个人一起过河) 。
如果河这边还有两个人，一个是第 $i$ 号，另外一个无关，河那边有 $i-2$ 个人，并且手电筒肯定在对岸，所以 $opt[i] = opt[i-2] + a[1] + a[i] + 2\times a[2]$ （让花费时间最少的人把电筒送过来，然后第 $i$ 个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题），所以 $opt[i] = min(opt[i-1] + a[1] + a[i], opt[i-2] + a[1] + a[i] + 2\times a[2] )$ 。
捡水果
https://www.jisuanke.com/course/736/37744
1000ms 131072K
蒜头在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，蒜头每下一个高度就可以捡起一个水果，并且获得水果的能量。山的形状如图所示：
1 3
2 1 2
3 6 2 3
43 5 4 1
这是一个高度为4的山，数字代表水果的能量。每次下一个高度，蒜头需要选择是往左下走，还是往右下走。例如：对于上图的情况，蒜头能获得的最大能量为，$3+1+6+5=15$。现在，蒜头希望你能帮他计算出下山能获得的最大能量。
输入格式
第一行输入一个 $n$，代表山的高度。（$1<n<=1000$）接下来 $n$ 行，第 $i+1$ 行有 $i$ 个数字，代表水果的能量，水果能量为正整数且不大于 $1000$。
输出格式
输出一个数字，代表下山一共获得的最大能量，占一行。
样例输入
14
23
31 2
46 2 3
53 5 4 1
样例输出
115
AC代码
1using namespace std;
2int main()
3{
4 int n, num;
5 int mou[1010] = {0};
6 int ans[1010] = {0};
7 scanf("%d", &n);
8 for (int k = 1; k <= n; ++k)
9 {
10 for (int i = 1; i <= k; ++i)
11 {
12 scanf("%d", &mou[i]);
13 }
14 for (int i = k; i >= 1; --i)
15 {
16 ans[i] = max(ans[i], ans[i - 1]) + mou[i];
17 }
18 }
19 int max = 0;
20 for (int i = 1; i <= n; ++i)
21 {
22 if (max < ans[i])
23 {
24 max = ans[i];
25 }
26 }
27 printf("%d", max);
28 return 0;
29}
逃生
https://www.jisuanke.com/course/736/37745
1000ms 131072K
蒜头君在玩一款逃生的游戏。在一个 $n \times m$ 的矩形地图上，蒜头位于其中一个点。地图上每个格子有加血的药剂，和掉血的火焰，药剂的药效不同，火焰的大小也不同，每个格子上有一个数字，如果格子上的数字是正数说明是一个药剂代表增加的生命值，如果是负数说明是火焰代表失去的生命值。
蒜头初始化有 $v$ 点血量，他的血量上限是 $c$，任何时刻他的生命值都不能大于血量上限，如果血量为0则会死亡，不能继续游戏。
矩形地图上的四个角 $(1,1)$， $(1,m)$， $(n,1)$， $(n,m)$ 为游戏的出口。游戏中只要选定了一个出口，就必须朝着这个方向走。例如，选择了左下的出口，就只能往左和下两个方向前进，选择了右上的出口，就只能往右和上两个方向前进，左上和右下方向的出口同理。
如果成功逃生，那么剩余生命值越高，则游戏分数越高。为了能拿到最高分，请你帮忙计算如果成功逃生最多能剩余多少血量，如果不能逃生输出-1。
输入格式
第一行依次输入整数 $n，m，x，y，v，c$（ $1 < n,m \leq 1000$ ， $1 \leq x \leq n$ ， $1 \leq y \leq m$ ， $1 \leq v \leq c \leq 10000$ ）, 其中 $n$, $m$ 代表地图大小，$(x,y)$ 代表蒜头君的初始位置，$v$ 代表蒜头的初始化血量，$c$ 代表蒜头的生命值上限。
接下来 $n$ 行，每行有 $m$ 个数字，代表地图信息。（每个数字的绝对值不大于100，地图中蒜头君的初始位置的值一定为0）
输出格式
一行输出一个数字，代表成功逃生最多剩余的血量，如果失败输出-1。
样例输入
14 4 3 2 5 10
21 2 3 4
3-1 -2 -3 -4
44 0 2 1
5-4 -3 -2 -1
样例输出
110
AC代码
1using namespace std;
2int mp[1010][1010];
3int dpv[1010][1010];
4int n, m, x, y, v, c;
5const int INF = 0x3f3f3f3f;
6int main()
7{
8 scanf("%d%d%d%d%d%d", &n, &m, &x, &y, &v, &c);
9 for (int i = 1; i <= n; ++i)
10 {
11 for (int j = 1; j <= m; ++j)
12 {
13 scanf("%d", &mp[i][j]);
14 }
15 }
16 dpv[x][y] = v;
17 // 01
18 for (int i = x; i <= n; ++i)
19 {
20 for (int j = y; j <= m; ++j)
21 {
22 if (i == x && j == y)
23 continue;
24 else if (i == x)
25 dpv[i][j] = dpv[i][j - 1] + mp[i][j];
26 else if (j == y)
27 dpv[i][j] = dpv[i - 1][j] + mp[i][j];
28 else
29 dpv[i][j] = max(dpv[i][j - 1], dpv[i - 1][j]) + mp[i][j];
30
31 if (dpv[i][j] >= c)
32 dpv[i][j] = c;
33 else if (dpv[i][j] <= 0)
34 dpv[i][j] = -INF;
35 }
36 }
37 // 02
38 for (int i = x; i >= 1; --i)
39 {
40 for (int j = y; j <= m; ++j)
41 {
42 if (i == x && j == y)
43 continue;
44 else if (i == x)
45 dpv[i][j] = dpv[i][j - 1] + mp[i][j];
46 else if (j == y)
47 dpv[i][j] = dpv[i + 1][j] + mp[i][j];
48 else
49 dpv[i][j] = max(dpv[i][j - 1], dpv[i + 1][j]) + mp[i][j];
50
51 if (dpv[i][j] >= c)
52 dpv[i][j] = c;
53 else if (dpv[i][j] <= 0)
54 dpv[i][j] = -INF;
55 }
56 }
57 // 03
58 for (int i = x; i <= n; ++i)
59 {
60 for (int j = y; j >= 1; --j)
61 {
62 if (i == x && y == j)
63 continue;
64 else if (i == x)
65 dpv[i][j] = dpv[i][j + 1] + mp[i][j];
66 else if (j == y)
67 dpv[i][j] = dpv[i - 1][j] + mp[i][j];
68 else
69 dpv[i][j] = max(dpv[i][j + 1], dpv[i - 1][j]) + mp[i][j];
70
71 if (dpv[i][j] >= c)
72 dpv[i][j] = c;
73 else if (dpv[i][j] <= 0)
74 dpv[i][j] = -INF;
75 }
76 }
77 // 04
78 for (int i = x; i >= 1; --i)
79 {
80 for (int j = y; j >= 1; --j)
81 {
82 if (i == x && y == j)
83 continue;
84 else if (i == x)
85 dpv[i][j] = dpv[i][j + 1] + mp[i][j];
86 else if (y == j)
87 dpv[i][j] = dpv[i + 1][j] + mp[i][j];
88
89 if (dpv[i][j] >= c)
90 dpv[i][j] = c;
91 else if (dpv[i][j] <= 0)
92 dpv[i][j] = -INF;
93 }
94 }
95
96 int ans = max(max(dpv[1][1], dpv[1][m]), max(dpv[n][m], dpv[n][1]));
97 if (ans > 0)
98 printf("%d", ans);
99 else
100 printf("-1");
101 return 0;
102}
蒜头君的新游戏
https://www.jisuanke.com/course/736/37746
1000ms 131072K
工作空闲之余，蒜头君经常带着同事们做游戏，最近蒜头君发明了一个好玩的新游戏：$n$ 位同事围成一个圈，同事 $A$ 手里拿着一个兔妮妮的娃娃。蒜头君喊游戏开始，每位手里拿着娃娃的同事可以选择将娃娃传给左边或者右边的同学，当蒜头君喊游戏结束时，停止传娃娃。此时手里拿着娃娃的同事即是败者。
玩了几轮之后，蒜头君想到一个问题：有多少种不同的方法，使得从同事 $A$ 开始传娃娃，传了 $m$ 次之后又回到了同事 $A$ 手里。两种方法，如果接娃娃的同事不同，或者接娃娃的顺序不同均视为不同的方法。例如 $1->2->3->1$ 和 $1->3->2->1$ 是两种不同的方法。
输入格式
输入一行，输入两个整数 $n,m(3 \leq n \leq 30,1 \leq m \leq 30)$ ，表示一共有 $n$ 位同事一起游戏，一共传 $m$ 次娃娃。
输出格式
输出一行，输出一个整数，表示一共有多少种不同的传娃娃方法。
样例输入
13 3
样例输出
12
提示
样例可以有 $1->2->3->1$ 和 $1->3->2->1$ 这两种不同的方法。
AC代码
1using namespace std;
2const int INF = 0x3f3f3f3f;
3
4int dp[40][40] = {{0}};
5
6int main()
7{
8
9 int n, m;
10 scanf("%d%d", &n, &m);
11
12 dp[1][2] = dp[1][n] = 1;
13
14 for (int i = 2; i <= m; i++)
15 {
16 for (int j = 1; j <= n; j++)
17 {
18 if (j == 1)
19 dp[i][j] = dp[i - 1][2] + dp[i - 1][n];
20 else if (j == n)
21 dp[i][j] = dp[i - 1][n - 1] + dp[i - 1][1];
22 else
23 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
24 }
25 }
26 printf("%d\n", dp[m][1]);
27
28 return 0;
29}
蒜头君的城堡之旅
https://www.jisuanke.com/course/736/37747
1000ms 131072K
蒜国地域是一个 $n$ 行 $m$ 列的矩阵，下标均从1开始。蒜国有个美丽的城堡，在坐标 $(n,m)$ 上，蒜头君在坐标 $(1,1)$ 的位置上。蒜头君打算出发去城堡游玩，游玩结束后返回到起点。在出发去城堡的路上，蒜头君只会选择往下或者往右走，而在返回的路上，蒜头君只会选择往上或者往左走，每次只能走一格。已知每个格子上都有一定数量的蒜味可乐，每个格子至多经过一次。
现在蒜头君请你来帮他计算一下，如何计划来回行程，可以收集到最多的蒜味可乐。
输入格式
第一行输入两个整数 $n,m(1 \leq n, m \leq 50)$ ，表示蒜国是一个 $n$ 行 $m$ 列的矩阵。
接下来输入 $n$ 行，每行输入 $m$ 个整数，代表一个 $n \times m$ 的矩阵，每个整数代表对应位置上的蒜味可乐数量，每行的每两个整数之间用一个空格隔开。其中蒜头君的位置和城堡的位置上没有蒜味可乐，用0表示，其余位置上的整数范围在 $[1,100]$ 内。
输出格式
输出一行，输出一个整数，表示蒜头君在来回路上能收集到的蒜味可乐的最大值。
样例输入
13 3
20 2 9
34 8 6
42 7 0
样例输出
136
提示
样例中，蒜头君可以选择这样的路线：$0->2->9->6->0->7->8->4->0$。
来回可以理解为同时从 $(1,1)$ 出发到 $(n,m)$ 的两条路径，这样思路也许会更清晰一些。
我们会发现 假设一个点走到 $(i,j)$ 另一个点走到 $(k,l)$ 这样状态就可以用 $dp[i][j][k][l]$ 来表示，时间复杂度为 $\mathcal{O}(n^4)$。其实还可以再进行优化，把4维的状态降低到3维，将复杂度优化到 $\mathcal{O}(n^3)$ ，这里就留给你自己来思考了。（本题目数据范围较小，不加优化也可以通过）
解题思路
-
看成两个独立的图，每个人都从他的起始点开始走，只是两个图的路线要求不重叠要达到一个坐标点，只有通过这个坐标点的上方或者左方进入，又已知路线不能重复，那么一旦从左方进入这个坐标，那么只能在上方离开这个坐标，反之亦然：从上方进入只能在左方离开。
-
那么这个问题（去到 $(n, m)$ 点并返回能取到的最多的可乐的数量）就可以分解为：从 $(1, 1)$ 出发到 $(n - 1, m)$ 路上取到的可乐加上从 $(n, m-1)$ 出发回到 $(1, 1)$ 的路上取到的可乐数量之和的最大值（或者相反）。
-
考虑到虽然出发和返回是两条路线，起始点不一样，但是最终连接的两个点却是一样的。那么就可以转化成这样：有两个人，同时在原点出发，目标都是城堡且两人路线不能重合，最后两个人可以取得的可乐的最大数量的和，就是这个题目的解。用（$x1，y1$）和（$x2，y2$）来表示这两个点，那么合法的两个点应当是：$x_1 \neq x_2 && y_1 \neq y_2$ (两点不能重复) $x_1 + y_1 == x_2 + y_2$ (两人同时出发，步数相同)
-
可以使用4维数组来表示这个问题的答案：$f[x1][y1][x2][y2]$，表示在原点出发后，两人分别到达点（$x1，y1$）和（$x2，y2$）时所取到的可乐的和的最大值。
我们先分阶段，把题意看做同时出发的两个人，同时到达终点 $(n,m)$ ，这两个人一共收集的最大数量。
因此 $dp[i][j][k][l]$ 看做同一时刻一个人到达 $(i,j)$，一个人到达 $(k,l)$ 所收集可乐的最大数量。
因此这一时刻的最大数量等于上一时刻的最大数量+刚刚捡到的可乐数量。
$$ \begin{align*} dp[i][j][k][l] = max(&max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]),\ &max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1]))\ & + a[i][j] + a[k][l]; \end{align*} $$
特殊情况：
1.两条路不能交叉，即当 $i==j&&k==l$ 时，要使 $dp[i][j][k][l]=0$；这样，这条路之后不会有人选，相当于这种情况不存在了。
2.最后，$dp[n][n][n][n]$ 一定为0，因为第一点，所以，我们只需要知道当一个人到达 $(n-1,m)/(n,m-1)$ 时，若要满足两人可乐数最大，另一个人一定达到 $(n,m-1)/(n-1,m)$ 处。答案输出 $dp[n][n-1][n-1][n]$ 即可。
3.把 $dp[51][51][51][51]$ 放在main函数外，全局变量所在的系统stack较大。
1using namespace std;
2
3const int maxn = 50 + 1;
4int a[maxn][maxn];
5int dp[maxn][maxn][maxn][maxn];
6
7int main()
8{
9 int n, m;
10 scanf("%d %d", &n, &m);
11 for (int i = 1; i <= n; i++)
12 for (int j = 1; j <= m; j++)
13 scanf("%d", &a[i][j]);
14
15 for (int i = 1; i <= n; i++)
16 {
17 for (int j = 1; j <= m; j++)
18 {
19 for (int k = 1; k <= n; k++)
20 {
21 int l = i + j - k;
22 if (l <= 0 || l > m)
23 continue;
24 if (i == k && j == l)
25 continue;
26 dp[i][j][k][l] = max(max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1]),
27 max(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])) +
28 a[i][j] + a[k][l];
29 }
30 }
31 }
32 printf("%d\n", dp[n - 1][m][n][m - 1]);
33 return 0;
34}