You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

4.2 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

数字三角形 【干货、背诵版】

基础题

AcWing 1015. 摘花生

二维状态表示,双重循环填充二维表,从上或左可以转移

  for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                // 递推的出发点,采用特判的办法手动维护,其它的靠关系式递推完成
                // 之所以这样对起点进行初始化,是因为只有这样才能保障逻辑自洽
                if (i == 1 && j == 1)
                    f[i][j] = w[i][j];
                else
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

初始化

 f[1][1] = w[1][1]; //出发点

状态表示 f[i][j]:走到第(i,j)个位置时可以获取到的最大数量和

状态转移 f[i][j]可以从哪些状态转移而来,答:从上方或左方过来

初始值 思考起点状态表示的现实含义

总结 ① 动态规划需要按上面的三步走,而最难的是状态表示,状态转移还好,根据题意推出相应的转换关系。状态表示靠 经验,对,是 经验

② 初始值:放在循环内初始化更直接

③ 一维状态表示,我理解不如二维直观,最起码思路应该是先有两维再缩成一维,而不是上来就直接一维。一般的题目不会对内存有严格的限制,能用二维还是二维吧,实在卡内存再考虑降为一维。

AcWing 1018. 最低通行费 与上一题基本一样,只不过是变换了下,需要你用思维转换一下:2n-1次,就是说只能向下或向右,否则次数就不达标了。还有一点,求最小值,而不是最大值,其它的没区别

//初始化为最大值
memset(f, 0x3f, sizeof f);

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        if (i == 1 && j == 1)
            f[i][j] = w[i][j]; //特事特办,不用追求完美的一体化表现,合理特判,逻辑简单
        else
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
    }

进阶题

AcWing 1027. 方格取数 走两次,其实是故意让我们真的走两回,每次取最优。

很明显,这是坑。因为如果每次走时不考虑别人,只考虑自己,就是局部最优,不是全局最优,这样就是贪心,不是动态规划。

解决办法就是把两次一起考虑,转化为有两个小人一起走,步调一致,此时两个相亲相爱,互相照顾,白头偕老,皆大欢喜:

状态表示也就呼之欲出:

状态表示 ① 两个坐标共同决定了现在的状态,换句话说,状态和上面的两个坐标都是相关的 ② 当你发现一维不足以表示当前状态时,考虑扩二维,二维不行再考虑扩三维,以此类推。

f[x_1][y_1][x_2][y_2]表示第1个人走到(x_1,y_1),第2个人走到(x_2,y_2),但需要保证x_1+y_1=x_2+y_2

状态转移 ① 如果两个人走到同一个位置,就可能加上一次这个位置上的数 ② 如果两个人走到不同的位置,就可以加上两个地方上的数

 //开始递推
for (int x1 = 1; x1 <= n; x1++)
    for (int y1 = 1; y1 <= n; y1++)
        for (int x2 = 1; x2 <= n; x2++)
            for (int y2 = 1; y2 <= n; y2++) {
                if (x1 + y1 == x2 + y2) {
                    int t = f[x1 - 1][y1][x2 - 1][y2];     //下下
                    t = max(t, f[x1][y1 - 1][x2][y2 - 1]); //右右
                    t = max(t, f[x1 - 1][y1][x2][y2 - 1]); //下右
                    t = max(t, f[x1][y1 - 1][x2 - 1][y2]); //右下
                    //加上这个点的数值
                    f[x1][y1][x2][y2] = t + w[x1][y1];
                    //如果这个点没有被重复走那么再加一次w(x2,y2)
                    if (x1 != x2 && y1 != y2) f[x1][y1][x2][y2] += w[x2][y2];
                }
            }

AcWing 275. 传纸条 与上面的题目是一个题。