首页 > [非常规面经] 0x01 “熟练掌握动态规划”
头像
toraoh
编辑于 2021-04-20 10:03
+ 关注

[非常规面经] 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
(另注:搜了一下,还有一些其他解法,比如记忆化搜索的,不过分析出向上走了后不能马上向下走是必须的。)

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐