动态规划

简介

动态规划 (Dynamic programming，简称 DP) 是美国数学家 Richard Bellman 在研究决策过程和控制系统理论时创建的新方法。它在数学上属于运筹学的一个分支，在数学、管理科学、计算机科学、经济学和生物信息学中均有应用，核心是通过把原问题分解为相对简单的子问题的方式来求解复杂问题，主要应用是求解决策过程最优的数学方法。

简单来讲，动态规划是一种算法思想，其核心是把问题分解为子问题，通过求解子问题进而解决当前问题。实际中，并非所有问题都可以通过动态规划来求解，通过动态规划解决的问题，对问题和其分解对子问题都有一定场景要求的，动态规划适用于有重叠子问题和最优子结构性质的问题，这类问题使用动态规划所耗时间往往比朴素解法更少。

如下图，我们对动态规划问题从应用场景、题解思路和常见示例题目三个方面来展开。

动态规划 Wiki

应用场景

重叠子问题

重叠子问题关注的是一个问题被分解为多个子问题时，子问题和子问题之间的关联。子问题会被重复计算，特别是我们使用递归自上向下对问题进行求解时，那动态规划是如何处理和优化这些子问题呢？我们以最简单的斐波那契数列为例来说明。

斐波那契数列

写一个函数，输入 n，求斐波那契 (Fibonacci) 数列的第 n 项 (即 F(N))。斐波那契数列的定义如下：
F(0) = 0,F(1) = 1
F(N) = F(N - 1) + F(N - 2)，其中 N > 1。

• 示例 1：

  • 输入：n = 2
  • 输出：1

• 示例 2：

  • 输入：n = 5
  • 输出：5

自上而下

通过我们可以通过自上而下的递归方法来处理该问题，代码如下

function fib(n: number): number {
    // n = 0, f(n) = 0;
    // n = 1, f(n) = 1;
    if (n < 2) return n

    return fib(n - 1) + fib(n - 2)
};

这样通过递归来解决，代码看起来很简洁，但是仔细分析下，当 n 取值较大时，这其中的重复计算可就太多了，如下，可以简单分解下

可以看到，f(n-2)、f(n-3) 等均进行了重复计算，可想而知，当数据量较大时，重复计算会更多，所以，递归实现代码很简单，计算却尤为耗费性能，可以尝试计算 n 取值为 100，看下计算时间。 那么，使用动态规划可以怎么求解这个问题呢

自下而上

我们可以从最简单的、规模最小的 f(0)、f(1) 开始计算，直到求解 f(n)，所以动态规划一般是不采用递归的方式，而是经由循环来完成计算的，看下代码

function fib(n: number): number {
    let dp = new Array(n).fill(0)

    // n = 0, f(n) = 0;
    // n = 1, f(n) = 1;
    dp[0] = 0, dp[1] = 1

    for (let i = 2; i <= n; i++){
        dp[i] = dp[i-1]+dp[i-2]
    }

    return dp[n]
};

可以看出，这种自下而上的解决方法，每次计算时都会用到上次的计算结果，从而可以规避大量的子问题重复计算

数组最大索引越界

针对本题，可能会超过数组的索引边界，所以需要额外处理下

function fib(n: number): number {
    let dp = new Array(n).fill(0), mod = 1000000007

    dp[0] = 0, dp[1] = 1

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
    }

    return dp[n] % mod
};

最优子结构

最优子结构关注的是当一个问题被分解为多个子问题时，子问题和原问题之间的关联。即问题的最优解所包含的子问题的解也是最优的，也就是说我们可以通过求解每个子问题的最优解来最后决定该问题的最优解

无后效性

子问题的解一旦确定，就不受其后问题的影响。具体来讲，就是子问题的解一旦确定，就不再改变

题解思路

动态规划问题的数学表达式可以简单的抽象为如下：dp[y] = f(dp[x]),x<y，一般常见解题思路，主要包含以下四步，其中最核心的是确定转移方程

• 状态定义：定义动态规划过程中涉及的变量状态
• 转移方程：归纳和抽象出子问题对应的数学方程
• 初始值：初始化时变量的取值
• 返回值：返回求解后所需要的值

我们以如下题目为入手来了解动态规划的常见解题思路

常见题目

动态规划常见的几种类型题目，⭐ 代表题目难度

最大子序和

：point_right： Leetcode 链接

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组 (子数组最少包含一个元素)，返回其最大和。

子数组是数组中的一个连续部分。

用例

• 示例 1：

  • 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  • 输出：6
  • 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

• 示例 2：

  • 输入：nums = [1]
  • 输出：1

思路分析

• 状态定义，本题核心是分析什么是最大和的连续子数组，这里我们可以用 f(n) 表示第 n 个数结尾的最大和的连续子数组
• 转移方程分析，显而易见，我们的问题就是求 [0, n] 这个区间里面 f(n) 的最大值，应用动态规划的划分子问题的方法，对 f(n) 来讲，其最大值可以通过比较 nums[n] 和 nums[n] + f(n-1)，取两者中较大值即可，从而，我们可以得出其转移方程为： f(n) = max{(f(n-1) + nums[n], nums[n])}
• 初始值分析，我们可以使用数组中第一个数来暂时表示最大值 max，随后，通过循环数组中所有项，代入转移方程，不断更新 max 取值即可
• 返回值即为 max

题解

function maxSubArray(nums: number[]): number {
    let max = nums[0], dp = [nums[0]], len = nums.length

    for (let n = 1; n < len; n++) {
        dp[n] = Math.max(0, dp[n - 1]) + nums[n]
        max = Math.max(max, dp[n])
    }

    return max
};

股票的最大利润 ⭐

Leetcode 链接

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

提示

• 示例 1：

  • 输入：[7,1,5,3,6,4]
  • 输出：5
  • 解释：在第 2 天 (股票价格 = 1) 的时候买入，在第 5 天 (股票价格 = 6) 的时候卖出，最大利润 = 6-1 = 5。 注意利润不能是 7-1 = 6，因为卖出价格需要大于买入价格。

• 示例 2：

  • 输入：[7,6,4,3,1]
  • 输出：0
  • 解释：在这种情况下，没有交易完成，所以最大利润为 0。

思路分析

和上题类似，我们首先思考 🤔，如何获取最大利润？按照常规思路，自然是最低点买入，最高点卖出

• 状态定义，我们可以用 f(n) 表示前 n 天的最大利润，min 表示前 n 天的最低价格
• 转移方程分析，可以预见的是，在 [0, n] 这个区间里面，f(n) 的最大值就是第 n-1 天的利润，第 n 天价格和前 n 天的最低价格 min 的较大值，即 f(n-1) 和 prices[n] - min 两者中的较大值，从而，我们可以得出其转移方程为： f(n) = max{(f(n-1), prices[n] - min)}
• 初始值分析，最小值 min 直接使用第一天的股票价格即可，max 赋值为 0，通过循环更新
• 返回值分析，返回值为 max

function maxProfit(prices: number[]): number {
    let min = prices[0], max = 0

    for (let n = 0; n < prices.length; n++) {
        min = Math.min(min, prices[n])
        max = Math.max(max, prices[n] - min)
    }

    return max
};

当然，本题也可以通过朴素循环求解，这里就不分析了，贴下代码

暴力法

function maxProfit(prices: number[]): number {
        let max = 0;
        for (let i = 0; i < prices.length - 1; i++) {
            for (let j = i + 1; j < prices.length; j++) {
                let profit = prices[j] - prices[i];
                if (profit > max) {
                    max = profit;
                }
            }
        }
        return max;
    }
}

最长上升子序列 ⭐⭐

：point_right： Leetcode 链接

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除 (或不删除) 数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例

• 输入：nums = [10,9,2,5,3,7,101,18]
• 输出：4
• 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4

思路分析

做了两道题目之后，你对动态规划有没有些感觉了呢 😜，我们接着来看这道经典的动态规划题，如何获取最长严格递增子序列？常规思路分析就是数组中后一个数比前面每一个都要大，一旦出现小的，连续性就不存在了

• 状态定义，我们可以用 f(n) 表示前 n 个上升子序列
• 转移方程分析，什么情况下我们可以确定数组中后一个数比前面每一个都要大？这里可以预见的是，使用双重循环，[0, n] 这个区间为外层循环，[0, m] 这个区间为内层循环，且 m< n，如果第 n 个数为上升子序列，则前 n 个数势必比任何一个 [f(0), f(m)] 的取值要大，所以其转移方程为： f(n) = max{(f(n), f(m)+1)}, m<n
• 初始值分析，最大值 max 赋值为 0，通过循环更新，dp 为长度为数组长度的新数组，其初始值均为 1
• 返回值分析，返回值为 max

function lengthOfLIS(nums: number[]): number {
    let len = nums.length, dp = new Array(len).fill(1), max = 0

    if (len === 0) return 0
    
    for (let i = 0; i < len; i++){
        for (let j = 0; j < i; j++){
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }

        max = Math.max(max, dp[i])
    }

    return max
};

这道题时间复杂度已经是 O(n^2) 了，思考下，有没有其他更优的解法呢？

最长递增子序列的个数 ⭐⭐⭐

：point_right： 题目链接

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例

• 输入：[1,3,5,4,7]
• 输出：2
• 解释：有两个最长递增子序列，分别是 [1，3，4，7] 和 [1，3，5，7]。

思路分析

这道题目是上一题的变形，上一题求解了最长递增子序列，那最长递增子序列是否只有一个呢？当然不是了，有几个，正是本题的求解目的

首先考虑下，这道题和上道题不同的地方在哪里，就是要在求解最长递增子序列的同时，记录其个数，那要怎么记录这个个数，就是本题的关键了，对于上个题目，我们给出的转移方程是 f(n) = max{(f(n), f(m)+1)}, m<n， 那对于有多少个这样的最长子序列，我们只需要将符合 f(n)=f(m) + 1 的组合挑选出来即可，所以给予之前的做法，我们只需要在对应条件内，再进行判断即可

• 状态定义，我们可以用 f(n) 表示前 n 个上升子序列
• 转移方程分析，什么情况下我们可以确定数组中后一个数比前面每一个都要大？这里可以预见的是，使用双重循环，[0, n] 这个区间为外层循环，[0, m] 这个区间为内层循环，且 m< n，如果第 n 个数为上升子序列，则前 n 个数势必比任何一个 [f(0), f(m)] 的取值要大，所以其转移方程为： f(n) = max{(f(n), f(m)+1)}, m<n，判断条件 f(n)=f(m) + 1
• 初始值分析，最大值 max 赋值为 0，通过循环更新，dp 为长度为数组长度的新数组，其初始值均为 1，count 为长度为数组长度的新数组，其初始值均为 1
• 返回值分析，返回值为 count

function findNumberOfLIS(nums: number[]): number {
    let len = nums.length, max = 0, res = 0, dp = new Array(len).fill(1), count = new Array(len).fill(1)

    for (let i = 0; i < len; i++){
        for (let j = 0; j < i; j++){
            if (nums[i] > nums[j]) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                } else if (dp[i] === dp[j] + 1) {
                    count[i] += count[j]
                }
            }
        }

        if (dp[i] > max) {
            max = dp[i]
            res = count[i]
        } else if(max === dp[i]) {
            res += count[i]
        }
    }

    return res
};

总结

本期动态规划通过四个常见题目，简要介绍了动态规划问题的常见解题思路，从状态定义、转移方程、初始值和返回值四方面进行了分析，其中转移方程是最核心的，而转移方程的确立来自对问题和子问题的梳理和分解，当你有了一个正确的转移方程，就已经成功了一大半，再考虑好相关边界取值，基本就大功告成了。

当然，动态规划可不止这些问题，比如：矩阵运算、前缀和、背包和路径压缩等问题，下一期我们将介绍进阶版本的动态规划，敬请期待。

链接