[非常规面经] 0x01 “熟练掌握动态规划”
1. 本系列不定期更新
2. 本系列假设读者有至少一种熟悉的编程语言，以及对面试中的常见算法有基本了解，不会对基本概念及其基本应用再做详述
3. 故事情节均为艺术创作需要，如有雷同，纯属巧合
4. 你不可能在面试中碰到这些题的啦，看过就好。 ……也许吧
-----------------------------------------------------
“看到你的简历上写了，'熟练掌握动态规划等算法'？”
“呃，是的。”
“那么，先说说动态规划的要素吧?”
"需要设计一下阶段，各个阶段要用什么状态表示，状态转移的方式，还有边界条件；状态和状态转移设计时要注意无后效性，……"(细节略去)
“嗯，可以的。那我们来做个题？”
设有 n×m 的方格图，每个方格中都有一个整数。
现有一只小熊，想从图的左上角走到右下角，每一步只能向下或向右走一格，并且不能走出边界。小熊会取走所有经过的方格中的整数，
求它能取到的整数之和的最大值。
现有一只小熊，想从图的左上角走到右下角，每一步只能向下或向右走一格，并且不能走出边界。小熊会取走所有经过的方格中的整数，
求它能取到的整数之和的最大值。
假设方格图最大1000 x 1000.
“啊，这个简单。
dp[x][y]表示从(0,0)走到(x,y)这个点的时候的最大值，转移时，只能从上面走下来或者左边走下来，两者取最大的。”
“那么代码实现一下？”
dp[0][0] = value[0][0];
for(int j = 1; j < m; j++){
dp[0][j] = dp[0][j - 1] + value[0][j];
}
for(int i = 1; i < n; i++){
dp[i][0] = dp[i - 1][0] + value[i][0];
for(int j = 1; j < m; j++){
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + value[i][j];
}
}
return dp[n - 1][m - 1]; "很快嘛，3分钟就写完了。看起来也没什么问题。
那我们把题目条件变一下：
这次，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，其他条件不变，仍然求能取到的整数之和的最大值。"
“嗯……” （长达10分钟的沉默）
“有什么想法吗？”
“抱歉，目前没有。”
“没事没事，我们换个题吧。”
--------------------------------------------------------------------
设有 n×m 的方格图，每个方格中都有一个整数。
现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，
求它能取到的整数之和的最大值。
有什么入手点吗？
如果是上下左右的确非常非常难做（能做吗？本人目前不知道），
但是只是上下和右，就比较有意思了：
我向右一步以后，再也没有办法进入左边的格子了。
这种做了以后再也没有退回去的选择的，可能意味着，按此划分阶段，后面的状态转移设计时，比较容易满足无后效性的要求。
（以下，第y列中，y从0开始，最左侧为第0列）
那么考虑，把到了 第y列 （或者说，向右走了y次） 设为阶段，
相应地，把第y列整列设为状态，整列整列地去转移，一列中每一行的元素和第一问一样，dp[x][y]表示从(0,0)走到(x,y)这个点的时候的最大值。
那么怎么做转移呢？
不妨先观察一个点，假设第y-1列已经算完了，考虑从第x行第y-1列到第y列
显然，先要向右走一步，从(x,y-1)到(x,y)
刚刚走过来的时候，我可以自由地：
- 向上
- 向下
- 停下来
但是，这时候，我一旦向上走了一步，我就再也不能向下了，因为再向下走，就破坏了不能重复经过已经走过的方格的限定条件，
不过我还可以不停地向上走，直到走到边界为止。
（向右后立刻向下走了一步同理，在此略去）
这样，我们有了一个初步的动态规划的设计：
- dp[x][y]表示从(0,0)走到(x,y)这个点的时候的最大值
- 整列整列地进行状态转移
- 对于一列中的每个点(0..n-1,y-1)，先向右走一步到(x,y)，然后分别枚举走到(0..x-1, y)和(x+1..n-1, y)（以及(x,y)）时总和是多少，更新dp[0..n-1][y]，每个位置保留最大值。
这时候的时间复杂度：
m列做转移*每次n行每个点*有n个终点=O(n^3)
（其实这样足够了，对于面试来说）
--------------------------------------------------------
考虑进一步优化：（已经不是动态规划设计的部分了，是状态转移的优化）
先把转移的式子写一下：
dp[x][y] = max(
///向右走一步后向下走到第x行
dp[0][y-1] + value[0][y] + value[1][y]+...+value[x-1][y] + value[x][y],
dp[1][y-1] + value[1][y] + value[2][y]+...+value[x-1][y] + value[x][y],
......,
dp[x-1][y-1] + value[x-1][y] + value[x][y],
///只向右走一步
dp[x][y-1] + value[x][y],
///向右走一步后向上走到第x行
dp[x+1][y-1] + value[x+1][y] + value[x][y],
......,
dp[n-1][y-1] + value[n-1][y] + value[n-2][y] + value[x+1][y] + value[x][y],
)
然后考虑一下dp[0][y], dp[1][y], dp[2][y]中，向右后不动或者向下的部分：
dp[0][y-1] + value[0][y],
dp[0][y-1] + value[0][y] + value[1][y],
dp[1][y-1] + value[1][y],
dp[0][y-1] + value[0][y] + value[1][y] + value[2][y],
dp[1][y-1] + value[1][y] + value[2][y],
dp[2][y-1] + value[2][y], 你发现了什么？
比较dp[1][y]和dp[2][y]所涉及的式子，可以简单得到一种生成办法：
1)在max()的列表中增加一项dp[2][y-1];
2)对max()的列表中的每一项，都+= value[2][y]
第二步对于max()的列表中的每一项的相对大小关系没有任何影响！
只有第一步，才有可能由最新的一项(dp[2][y-1])改变最大值，变成更大的！
所以，之前O(n^3)的做法中有大量的重复计算，我们可以优化一下：
从上到下扫一遍，dp_top_to_bottom[x][y] = max(dp[x-1][y] , dp[x][y-1]) + value[x][y]
dp[x-1][y] 代表了上面走下来的各项中最大的， dp[x][y-1]表示当前点左侧的点（前一列的对应点），直接向右走一步，两者取最大的，再加上当前点的值。
从下到上，搞个类似的dp_bottom_to_top[x][y]，从下到上扫一遍。
最后，
dp[x][y]= max(dp_top_to_bottom[x][y], dp_bottom_to_top[x][y]);
这样的时间复杂度：
m列做转移*（从上到下扫一遍n+从下到上扫一遍n）=O(n^2)
恭喜，这样有100分了
示例代码：
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m;
int a[1005][1005];
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &a[i][j]);
}
}
ll f[2][1005];
ll tmp[2][1005];
f[0][0] = a[0][0];
for (int i = 1; i < n; i++) {
f[0][i] = f[0][i - 1] + a[i][0];
}
for (int j = 1; j < m; j++) {
ll* f1 = f[(j & 1) ^ 1];
ll* f2 = f[(j & 1)];
//top->bottom
tmp[0][0] = f1[0] + a[0][j];
for (int i = 1; i < n; i++) {
tmp[0][i] = max(f1[i], tmp[0][i - 1]) + a[i][j];
}
//bottom->top
tmp[1][n - 1] = f1[n - 1] + a[n - 1][j];
for (int i = n - 2; i >= 0; i--) {
tmp[1][i] = max(f1[i], tmp[1][i + 1]) + a[i][j];
}
for (int i = 0; i < n; i++) {
f2[i] = max(tmp[0][i], tmp[1][i]);
}
}
printf("%lld\n", f[(m - 1) & 1][n - 1]);
} --------------------------------------------------------
题源： CCF CSP 2020 入门级（Junior） 第二轮 T4 方格取数 number https://ac.nowcoder.com/acm/problem/213852 https://www.sohu.com/a/430275027_821349
（入门级Junior，参与人员主要是初中生）
（不知道当时有多少人这题拿了100分；作为参考，浙江省当时21人拿了400分 满分， 初一初二初三均有 https://www.qsnkj.org.cn/#/report/detail/20210106113243732 ）
（另注：搜了一下，还有一些其他解法，比如记忆化搜索的，不过分析出向上走了后不能马上向下走是必须的。）
投递华泰证券等公司7个岗位 >