经典例题：数字三角形

· · 个人记录

话说距离上一次博客更新已经有一段时间了 我才不说是因为老师留作业呢 ，那么我们来复习一下动规的有关知识吧。

既然是动规，肯定离不开一道经典的例题：数字三角形。

有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数。

从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来，如何走才能使得这个和尽可能大？

首先我们可以想到一个可爱的暴力回溯法：每次都可以做出向左下或右下行走的选择，那么我们可以递归枚举所有可行路线，从最后一层回溯时更新答案。

但是很显然这样做的话时间复杂度让人难以接受，因为完整的路线一共有 2^(n-1) 条，可以说是最糟糕的了。

那么怎么做呢？

我们可以先考虑这样一个问题：

从最后一行的某一个数开始，每次可以往左上或右上走一格，如何走才能使沿途经过的数加和尽可能大？

显然不论从最后一行的那个数开始走，每次选择值最大的数走，答案最优； 下面是口胡部分 因为每往上一层，可选择的数的总数就会减少一个，最终你就无可选择了，那还不如一开始选择大一点的，省的最后血本无归。

现在把刚刚那个问题反过来，可以看到，这样行走的方式其实也适用于原问题；换句话说，我们如果想保证当前这一格位置出发的加和最大，就必须保证下一步是走向左下和右下中从那里出发数值较大的一个。

现在回到动归本身，前辈有云：

动态规划的核心是状态和转移方程。

那么这个问题的状态定义即为： f[i][j] 为从第 i 行第 j 列出发能得到的最大值。

相应的，状态转移方程为： f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1])

问题来了，如果我们想知道的不是最优解，而是次优解甚至第几优的解呢？

其实细致地思考一下，如果我们选择了 f[i + 1][j] 作为 f[i][j] 的最优解，那么 f[i + 1][j + 1]对于 f[i][j] 来说不就是次优解吗？同样的道理，如果我们选择f[i + 1][j] 的第 k 优解作为 f[i][j] 的第 k 优解，那么 f[i + 1][j + 1] 的第 k 优解就是 f[i][j] 的第 k - 1 优解；这是因为 f[i + 1][j + 1] 的第 k 优解肯定优于第 k - 1 优解。

相应得到状态定义： f[i][j][k] 为从第 i 行第 j 列出发得到的第 k 优解。

转移方程 其实是我太懒了了不想写：

for (int i = n - 1; i >= 1; i--)
    for (int j = 1; j <= i; j++)
    {
        int cnt1 = 1, cnt2 = 1;
        for (int tk = 1; tk <= k; tk++)
            if (f[i + 1][j + 1][cnt2] > f[i + 1][j][cnt1])
            {
                f[i][j][tk] = f[i + 1][j + 1][cnt2] + a[i][j];
                cnt2++;
            }
            else
            {
                f[i][j][tk] = f[i + 1][j][cnt1] + a[i][j];
                cnt1++;
            }
    }

引用资料：《算法竞赛入门经典》