深入浅出理解动态规划（二） | 最优子结构

我们在《深入浅出理解动态规划（一） | 交叠子问题》中讨论过，使用动态规划能解决的问题具有下面两个主要的性质：

第一，交叠子问题

第二，最优子结构

本期讨论动态规划的主要性质--最优子结构。

最优子结构

对于一个给定的问题，当该问题可以由其子问题的最优解获得时，则该问题具有“最优子结构”性质。

例如，“最短路径”问题具有如下的“最优子结构”性质：

如果一个结点x在从起点u到终点v的最短路径上，则从u到v的最短路径由从u到x的最短路径和从x到v的最短路径构成。像Floyd-Warshall（弗洛伊德—沃舍尔）和Bellman-Ford（贝尔曼—福特）算法就是典型的动态规划的例子。

另外，“最长路径”问题不具有“最优子结构”性质。我们这里所说的最长路径是两个节点之间的最长简单路径（路径没有环），由CLRS（Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein）编写的《算法导论》（Introduction to Algorithms）这本书中给出了下面的无权图。

从q到t有两条最长的路径：q→r→t与q→s→t。与最短路径不同，这些最长路径没有“最优子结构”性质。例如，最长路径q→r→t不是由q 到r的最长路径和r到t的最长路径构成的，因为从q到r的最长路径是 q→s→t→r，从r到t的最长路径是r→q→s→t。

经典例题：数字三角形

题目描述：

下图给出了一个数字三角形，从三角形的顶部到底部有很多条不同的路径，对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入：

输入一个正整数N (1 < N <= 100)，给出三角形的行数，下面的N行给出数字三角形，数字三角形上的数的范围都在0和100之间。

输出：

输出最大的和。

样例输入：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样例输出：

30

解题思路：

动态规划通常用来求最优解。能用动态规划解决的求最优解问题，必须满足最优解的每个局部解也都是最优的。以上题为例，最佳路径中的每个数字到底部的那一段路径，都是从该数字出发到底部的最佳路径。

实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子中，有递推公式：

不需要写递归函数，从最后一行的元素开始向上逐行递推，就能求得最终 dp[1][1]的值。程序如下：

#include<stdio.h>
#include<string.h>

#define MAX_NUM 1000
int D[MAX_NUM + 10][MAX_NUM + 10];  /* 存储数字三角形 */
int N;                                    /* 数字三角形的行数 */
int dp[MAX_NUM + 10][MAX_NUM + 10]; /* 状态数组 */

int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    int i, j;

    scanf("%d", &N);

    memset(dp, 0, sizeof(dp));/* 状态数组全部初始化为0 */

    for (i = 1; i <= N; ++i)
        for (j = 1; j <= i; ++j)
            scanf("%d", &D[i][j]); /* 输入数字三角形 */

    for (j = 1; j <= N; j++) { /* 处理最底层一行 */
        dp[N][j] = D[N][j]; /* 最底层一行状态数组的值即为该数字本身 */
    }

    for (i = N - 1; i >= 1; i--) { /* 从倒数第二层开始直至最顶层 */
        for (j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + D[i][j];
        }
    }

    printf("%d\n", dp[1][1]);       /* 顶点（1,1）即为最大值 */s

    return 0;
}

如下图所示，方框里的数字是能取得的最大值。相信大家看完这个图，对动态规划的理解不那么困难了。

实际上，因为dp[i][j]的值在用来计算出dp[i-1][j]后已经无用，所以可以将计算出的dp[i-1][j]的值直接存放在dp[i][j]的位置。这样，计算出 dp[N-1][1]替换原来的 dp[N][1]，计算出 dp[N-1][2]替换原来的dp[N][2]......计算出 dp[N-1][N-1]替换原来的 dp[N][N-1]，dp数组实际上只用最后一行，就能够存放上面程序中本该存放在dp[N-1]那一行的全部结果。同理，再一行行向上递推，dp数组只需要最后一行就可以存放全部中间计算结果，最终的结果（本该是dp[1][1])也可以存放在dp[N][1]）。因此，实际上dp不需要是二维数组，一维数组就足够了。

改写后的程序如下：

#include<stdio.h>
#include<string.h>

#define MAX_NUM 1000
int D[MAX_NUM + 10][MAX_NUM + 10];  /* 存储数字三角形 */
int N;    /* 数字三角形的行数 */
int *dp; /* 状态数组 */

int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    int i, j;

    scanf("%d", &N);

    for (i = 1; i <= N; ++i)
        for (j = 1; j <= i; ++j)
            scanf("%d", &D[i][j]); /* 输入数字三角形 */

    dp = D[N];  /* dp指向第N行 */

    for (i = N - 1; i >= 1; i--) { /* 从倒数第二层开始直至最顶层 */
        for (j = 1; j <= i; j++) {
            dp[j] = max(dp[j], dp[j + 1]) + D[i][j];
        }
    }

    printf("%d\n", dp[1]);       /* （1,1）即为最大值 */

    return 0;
}

这种用一维数组取代二维数组进行递推、节省空间的技巧叫“滚动数组”。上面的程序虽然节省了空间，但是没有降低时间复杂度，时间复杂度依然是O(N^2)的，从程序使用了两重循环就可以看出。

总结

许多求最优解的问题可以用动态规划来解决。用动态规划解题，首先要把原问题分解为若干个子问题，这一点和前面的递归方法类似。区别在于，单纯的递归往往会导致子问题被重复计算，而用动态规划的方法，子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。

子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的n变成n-1, 或从原来的n×m变成n×（m-1）。找到子问题，就意味着找到了将整个问题逐渐分解的办法，因为子问题可以用相同的思路一直分解下去，直到最底层规模最小的子问题可以一目了然地看出解（像上面数字三角形的递推公式中，当i=N时，解就可以直接得到）。每一层子问题的解决会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程时就不需要写递归函数了。

文章推荐

推荐一：深入浅出理解动态规划（一） | 交叠子问题,文章内容：动态规划--交叠子问题（记忆化搜索算法、打表法求解第n个斐波那契数）。