“动态规划”第 2 节：第 1 个动态规划问题的 3 种实现

动态规划

例题

例1：LeetCode 第 70 题：Climbing Stairs

题目要求：有一个楼梯，总共有 $n$ 阶台阶。每一次，可以上一个台阶，也可以上两个台阶。问，爬上这样的一个楼梯，一共有多少不同的方法？

• 如 $n = 3$，可以爬上这个楼梯的方法有：$[1,1,1] , [1,2] , [2,1]$；
• 所以答案为 $3$。

思路分析：我们可以画出这个问题的递归结构图。

我们可以发现：1、该图是一个树形结构图；2、有重叠子问题。

递归实现

Java 代码：

public class Solution {
    public int climbingStairs(int n) {
        if (n <= 0) {
            return 1;
        }
        int res = climbinng(n);
        return res;
    }
    private int climbinng(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) { // 方法1：一个台阶，一个台阶；方法2：一次上两个台阶
            return 2;
        }
        // 接下来就是看图说话了(乘法计数原理)
        return climbinng(n - 1) * 1 + climbinng(n - 2) * 1;
    }
}

说明：从第 1 节我们可以知道，这一版代码有大量的“重叠子问题”，我们应该加上缓存。

使用记忆化搜索

public class Solution {
    private int[] memory;
    public int climbingStairs(int n) {
        if (n <= 0) {
            return 1;
        }
        memory = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            memory[i] = -1;
        }
        int res = climbinng(n);
        return res;
    }
    private int climbinng(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) { // 方法1：一个台阶，一个台阶；方法2：一次上两个台阶
            return 2;
        }
        // 接下来就是看图说话了(乘法计数原理)
        if (memory[n] == -1) {
            memory[n] = climbinng(n - 1) * 1 + climbinng(n - 2) * 1;
        }
        return memory[n];
    }
}

说明：递归的代码写起来比较繁琐，我们可以用于思考。另一种写法就是“自底向上”，即“动态规划”。“动态规划”的代码是比较简洁的。

使用动态规划

Java 代码：

public class Solution2 {
    public int climbingStairs(int n) {
        if (n <= 0) {
            return 1;
        }
        if (n == 1) {
            return 2;
        }
        int[] memory = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            memory[i] = -1;
        }
        for (int i = 2; i < n + 1; i++) {
            memory[i] = memory[i - 1] + memory[i - 2];
        }
        return memory[n + 1];
    }
}

练习

练习1：LeetCode 第 120 题： 三角形最小路径和

要求：给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小。(每一步只能移动到相邻的格子中。)

分析：关键的地方在于“从上到下”和“从下到上”思考的路径不同，导致解答的复杂程度不同。

“从上到下”：最边上的点只能从最边上的点走过来。

“从下到上”：每一点都有两个孩子：左孩子和右孩子，可以少掉很多讨论。

Python 实现：

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0:
            return 0
        # 这里要多留一个位置，防止数组越界
        dp = [0] * (len(triangle) + 1)
        for i in range(len(triangle) - 1, -1, -1):
            for j in range(i + 1):
                # 【关键】自底向上，每个元素都有左右孩子，就相当于在最后一行加上一行 0
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
            print(dp)
        return dp[0]
if __name__ == '__main__':
    triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
    # triangle = [[-10]]
    s = Solution()
    res = s.minimumTotal(triangle)
    print(res)

二刷的时候，写的代码：

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        l = len(triangle)
        if l == 0:
            return 0
        dp = triangle[-1]
        for i in range(l - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        return dp[0]

练习2：LeetCode 第 64 题：最小路径和

要求：给出一个 m * n 的矩阵，其中每一个格子包含一个非负整数。寻找一条从左上角到右下角的路径，使得沿路的数字和最小。

• 每一步只能左移或者下移。

参考解答：

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        if m == 0:
            return 0
        n = len(grid[0])
        for col in range(1, n):
            # 第 0 行特殊处理
            grid[0][col] += grid[0][col - 1]
        for row in range(1, m):
            grid[row][0] += grid[row - 1][0]
            for col in range(1, n):
                grid[row][col] += min(grid[row - 1][col], grid[row][col - 1])
        return grid[-1][-1]

（完）