计蒜客的动态规划总结，现在感觉太水了，暂时放放
递推
递推也是经常被使用的一种简单算法。递推是一种用若干步可重复的简单运算来描述复杂问题的方法。
递推的特点在于，每一项都和他前面的若干项有一定关联，这种关联一般可以通过递推关系式来表示，可以通过其前面若干项得出某项的数据。
对于递推问题的求解一般从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得出想要的结果，这种求解问题的方法叫递推法。其中，初始的若干数据项称为边界。
兔子繁殖问题
已知一对兔子，每个月可以生一对小兔子，小兔子出生后的第二个月会变为成年兔子，会继续生小兔子。
第一个月，我们有1对小兔子。 第二个月，我们有1对成年的兔子。 第三个月，我们有1对成年的兔子，有1对小兔子，共2对。 第四个月，我们有2对成年的兔子，有1对小兔子，共3对。 第五个月，我们有3对成年的兔子，有2对小兔子，共5对。 ……
现在，我们希望知道第 $n$ 个月，一共有多少只兔子。（兔子身体素质好，不会死掉。）
有可能你已经发现了规律了，但是我们还是要来理智地分析一下。
设第 $i$ 个月的兔子数量为 $F_i$ ，第 $i$ 月的成年兔子数量为 $a_i$ ，第 $i$ 月的小兔子数量为 $b_i$ ，那么 $F_i = a_i + b_i$ 。
第 $i$ 月的成年兔子，由第 $i-1$ 个月的小兔子长大与第 $i-1$ 月的成年兔子得到，也就是说，第 $i-1$ 个月兔子的总数量， $a_i = a_{i-1} + b_{i-1} = F_{i-1}$ 。
第 $i$ 个月的小兔子，是由第 $i-1$ 个月的成年兔子生的，也就是第 $i-2$ 个月的成年兔子和小兔子，也就是 $i-2$ 个月兔子的总数量， $b_i = a_{i-1} = a_{i-2} + b_{i-2} = F_{i-2}$ 。
这样，我们就找到了这个题目的递推关系式。如果用 $F_i$ 代表第 $i$ 个月兔子的总数量，那么递推关系式为： $F_i = F_{i-1} + F_{i-2}$ 。边界值，我们知道 $F_1 = 1，F_2 = 1$ 。那么，我们就可以写出这个题目的代码了。
1 f[1] = 1, f[2] = 1;
2 for (int i = 3; i <= n; ++i) {
3 f[i] = f[i - 1] + f[i - 2];
4 }
5 // f[n]即为所求。
装错信封问题
某君写了 $n$ 封信，并且有 $n$ 个信封，如果所有的信都装错了信封，那么会有多少种不同的情况？
这个题目，相信你就没有办法像上一道题目一样不通过分析直接猜出答案了吧。那我们来分析一下。
我们用 $F_n$ 来表示 $n$ 封信和 $n$ 个信封全部装错的方案数。
-
第一步，把第 $n$ 封信放在第 $m$ 个信封 $(m \neq n)$，一共有 $n-1$ 种方法。
-
第二步，放第 $m$ 封信的时候，有两种可能：
-
把第 $m$ 封信放在第 $n$ 个信封里，这样对于剩下的 $n-2$ 封信全部放错方案数就是 $F_{n-2}$ 种。
-
不让第 $m$ 封信放在第 $n$ 个信封里。这样对于除第 $n$ 封以外的 $n-1$ 封信，放到剩余的 $n-1$ 个信封且全部放错，就有 $F_{n-1}$ 种方案数。(不理解这一步的同学，可以想一下，这 $n-1$ 封信里面，除第 $m$ 封信以外每个信都不能放对应的正确信封，第 $m$ 个信不能放第 $n$ 个信封，这样 $n-1$ 封信，每个信有且仅有一个对应的不能放置的信封，那么方案数就是 $F_{n-1}$)
这样，这一步共有 $F_{n-2} + F_{n-1}$ 种方案数。
-
到这里，我们已经可以得出这个递推式了，根据乘法原理： $F_n = (n-1) * (F_{n-1} + F_{n-2})$ 。
我们再想一下，代码中的初始条件，也就是边界值。在只有一封信的时候，不可能装错，那么 $F_1 = 0$ ；有两封信的时候，装错的方案数为 $F_2 = 1$ 。
现在我们初始条件和递推公式全有了，那么可以写代码了。
1 for (int i = 3; i <= n; ++i) {
2 F[i] = (i - 1) * (F[i - 1] + F[i - 2]);
3 }
4 // F[n]即为答案
马踏过河卒问题
https://www.jisuanke.com/course/736/37740
1000ms 131072K
$A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的 $C$ 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 $C$ 点上的马可以控制9个点（图中的 $P1,P2 \cdots P8 和 C$ ）。卒不能通过对方马的控制点。
棋盘用坐标表示，$A$点 $(0，0)$、$B$ 点 $(n，m)$、C点 $(c_x, c_y)$ ($0 < c_x < n \leq 20$ ， $0 < c_y < m \leq 20$ )。现在要求你计算出过河卒从 $A$ 点能够到达 $B$ 点的路径的条数。注：象棋中马走“日”。
输入格式
输入4个整数，$n$，$m$， $c_x$， $c_y$，分别表示 $B$ 点的横纵坐标和 $C$ 点的横纵坐标。
输出格式
输出一个整数，代表从A点走到B点的所有路径数。
样例输入
15 5 2 4
样例输出
114
提示
注意答案有可能会很大，超过int数据类型的范围，你需要用到long long数据类型。
解题思路
根据题目的要求，卒只能向下或者向右走，那么想要到达棋盘上的一个点，有两种方式：从左边的格子过来，或者从上边的格子过来。所以，过河卒到达某点的路径数目等于到达与其相邻的左边点和上边点的路径数目和。我们用 $F_{i,j}$ 来表示到达点 $(i,j)$ 的路径数目。所以递推式为： $F_{i,j} = F_{i-1,j} + F_{i, j-1}$ 。我们根据递推式发现，我们可以用逐行或逐列的递推方法求出从起点到终点的路径数目。我们来想一下边界条件，因为 $(0，0)$ 是卒的起始位置，那么 $F_{0,0} = 1$ 。
我们再想一下如何处理马控制的点。马控制的点的路径数一定是0，这样其实并不影响我们做递推，只要遇到了马控制的点，直接设置为0就可以了。所以，我们需要提前标记出哪些点是马控制的点。我们可以用两个一维数组来表示马的横向位移和纵向位移，这样来方便我们计算马的控制点，然后使用一个二维数组来标记某个点是否是马控制的点。
AC代码
墙壁涂色
https://www.jisuanke.com/course/736/37741
1000ms 131072K
蒜头君觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了3种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 $n$ 个部分，蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。
例如，当 $n=5$ 时，下面就是一种合法方案。
蓝 红 黄 红 黄
由于墙壁是一个环形，所以下面这个方案就是不合法的。
蓝 红 黄 红 蓝
输入格式
一个整数n，表示房间被划分成多少部分。（ $1 \leq n \leq 50$ ）
输出格式
一个整数，表示给墙壁涂色的合法方案数。
样例输入
14
样例输出
118
提示
找出 $ans[n]$ 与 $ans[n-1]$ 和 $ans[n-2]$ 的关系。
考虑第1块和 $n-1$ 块颜色不一样的情况，现在第 $n$ 块要和第 $n-1$ 和 $1$ 都不一样，但是只有3种颜色，所以 $n$ 只有一种颜色选择，这种情况方案数正好是 $ans[n-1]$ 。
考虑第1块和 $n-1$ 块颜色一样的情况，第 $n-2$ 块必然要和第 $n-1$ 块不同，同时也就和第1块不同，前面 $n-2$ 块方案数是 $ans[n-2]$，第 $n$ 块要和第1块和第 $n-1$ 块不同，有2种选择，所以这种情况方案数是 $2*ans[n-2]$ 。
上面2种情况加起来就是总方案数。
AC代码
1#include<bits/stdc++.h>
2using namespace std;
3
4int main()
5{
6 long long ans[60];
7 int n;
8 ans[1] = 3;
9 ans[2] = 6;
10 ans[3] = 6;
11 scanf("%d", &n);
12 if (n <= 3)
13 printf("%lld", ans[n]);
14 else
15 {
16 for (int i = 4; i <= n; ++i)
17 {
18 ans[i] = ans[i - 1] + ans[i - 2] * 2;
19 }
20 printf("%lld", ans[n]);
21 }
22 return 0;
23}
杨辉三角
https://www.jisuanke.com/course/736/37742
1000ms 131072K
杨辉三角是二项式系数在三角形中的一种几何排列。它的每个数等于它上方两数之和，每行数字左右对称，由1开始逐渐变大。
1 1
2 1 1
3 1 2 1
4 1 3 3 1
5 1 4 6 4 1
61 5 10 10 5 1
请求出杨辉三角的第 $n$ 行，第 $m$ 项的数字是什么。
输入格式
第一行输入两个整数 $n$，$m$代表行数和列数。（ $1 \leq n,m \leq 50$ ）
输出格式
输出一个整数，代表杨辉三角的第 $n$ 行，第 $m$ 项的数字。
样例输入
16 3
样例输出
110
AC代码
1using namespace std;
2int main()
3{
4 int n, m;
5 scanf("%d%d", &n, &m);
6 long long ans[60][60];
7 memset(ans, 0, sizeof(ans));
8 ans[1][1] = 1;
9 for (int i = 2; i <= n; ++i)
10 {
11 for (int j = 1; j <= m; ++j)
12 {
13 if (j == 1)
14 ans[i][j] = 1;
15 else
16 {
17 ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
18 }
19 }
20 }
21 printf("%lld", ans[n][m]);
22 return 0;
23}
动态规划入门
动态规划是编程解题的一种重要手段。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}
背包问题
给定一组物品，每种物品都有自己的重量（体积）和价值，现有一个背包，在受限制的重量（或者容积）下，取若干物品，使得总价值最大。这一类问题，被称为背包问题。
题目描述
当前有 $N$ 件物品和一个承重量为 $V$ 的背包。已知第i件物品的重量是 $w[i]$，价值是 $v[i]$。
由于每种物品有且仅有一件，因此只能选择放或不放，我们称之为01背包问题。
现在你需要选出若干件物品，在它们的重量之和不超过C的条件下，使得价值总和尽可能大。
对于每个物品是否要装入背包，我们自然可以进行暴力枚举或搜索，但是如果要暴力地去做，那么时间复杂度会非常的高，这时候需要一种更加优化的算法——动态规划。
解析
对于 01 背包，先确定这个问题的状态。共有 $N$ 个物品，背包总承重为 $V$，那么可以根据物品和容量来确定一个状态。前 $i$ 个物品，放在背包里，总重量不超过 $j$ 的前提下，所获得的最大价值为 $dp[i][j]$。
是否将第 $i$ 个物品装入背包中，就是决策。为了使价值最大化，如果第 $i$ 个物品放入背包后，总重量不超过限制且总价值比之前要大，那么就将第 $i$ 个物品放入背包。根据这个逻辑写出转移方程：
$$ \begin{align*} \displaystyle \forall\ j < w[i], dp[i][j] &= dp[i-1][j]\ \displaystyle \forall\ w[i] \le j \le C, dp[i][j] &= max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]) \end{align*} $$
为了更好地理解这个转移方程，看一个具体的例子。有 5 个物品，编号1-5，重量分别是 $[2,2,6,5,4]$，价值分别是 $[6,3,5,4,6]$，背包的总承重为 10。
列出本问题中所有的状态变量，也就是转移方程中的 $dp$ 变量，且初始化为0。当第一个物品放入背包，因为第一个物品重量为2，价值为6，只要背包容量大于等于2，都可以放第一个物品，根据我们的转移方程 $dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i]$ ，那么：
根据我们的转移方程继续放第二个物品，容量为2，3的时候： $dp[i-1][j-w[i]] + v[i] < dp[i-1][j]$ ，则 $dp[i][j] = dp[i-1][j]$ 。
容量大于3的时候： $dp[i -1][j-w[i]] + v[i] > dp[i-1][j]$ ，则 $dp[i][j] = dp[i-1][j-w[i]] + v[i]$ 。dp变量被更新为：
当放第3个物品的时候，第三个物品的重量 $w[i]=6$ ，所以在背包容量 $j<w[i]$ 的时候，$dp[i][j] = dp[i-1][j]$。在背包容量 $j \ge v[i]$ 的时候 $dp[i][j] = max(dp[i-1][j], dp[i - 1][j - w[i]] + v[i])$。
以此类推，把剩余的物品全部根据转移方程放入背包后，dpdp 变量为：
通过上面的表格，可以知道当这 5 个物品放入容量为 10 的背包中，最大的价值是 15，也就是 $dp[5][10] = 15$。
1for (int i = 1; i <= N; ++i) {
2 for (int j = 0; j <= V; ++j) {
3 if(j >= w[i]) {
4 dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
5 }
6 else {
7 dp[i][j] = dp[i-1][j];
8 }
9 }
10}
时间上是两重循环，时间复杂度为 $\mathcal{O}(NV)$。
空间是二维的，空间复杂度也为 $\mathcal{O}(NV)$。
优化空间复杂度
空间复杂度还可以优化到 $\mathcal{O}(V)$ ，但时间复杂度已经很难再优化了。
当前计算第 $i$ 件物品，总重量为 $v$ 的最大价值。我们注意到，它需要的状态是 $dp[i-1][0\ldots v]$ 。
如果从大到小，也就是从 $V$ 到 0 枚举，则当前引用的 $dp[v]$ 和 $dp[v-w[i]]$，仍然是计算第 $i-1$ 件物品的结果，即 $dp[i-1][v],dp[i-1][v-w[i]]$，那么这一维的状态是冗余的。
故我们可以化简转移方程：$dp[j]=max(dp[j-w[i]]+v[i],dp[j])$。
1for (int i = 1; i <= n; ++i)
2 for (int j = v; j >= w[i]; --j)
3 dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
这个做法的空间复杂度为 $\mathcal{O}(V)$ 。