动态规划

认识动态规划

动态规划(英语: Dynamic Programming，简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

动态规划的名字来源于20世纪50年代的一个美国数学家 Richard Bellman

他在处理一类具有重叠子问题和最优子结构性质的问题时，想到了一种"动态"地求解问题的方法
它通过将问题划分为若干个子问题，并在计算子问题的基础上，逐步构建出原问题的解
他使用"动态规划"这个术语来描述这种方法，并将它应用于各种领域，如控制论、经济学、运筹学等

动态规划(Dynamic Programming，可以简称DP)是一个非常重要的算法思想：

在算法竞赛、数据结构、机器学习等领域中，动态规划都是必不可少的知识之一

动态规划的核心思想是"将问题划分为若干个子问题，并在计算子问题的基础上，逐步构建出原问题的解"

具体地说，动态规划通常涉及以下四个步骤：

定义状态
- 将原问题划分为若干个子问题，定义状态表示子问题的解，通常使用一个数组或者矩阵来表示
确定状态转移方程
- 在计算子问题的基础上，逐步构建出原问题的解
- 这个过程通常使用"状态转移方程"来描述，表示从一个状态转移到另一个状态时的转移规则
初始化状态
计算原问题的解(最终答案)
- 通过计算状态之间的转移，最终计算出原问题的解
- 通常使用递归或者迭代(循环)的方式计算

这四个步骤是动态规划的核心思想，其中状态定义和状态转移方程是动态规划的关键

斐波那契数列是一个经典的数列，在自然界中很多地方都可以找到，它的定义如下:

第 0 个和第 1 个斐波那契数分别为 0 和 1，即 F0=0, F1=1
从第2个数开始，每个斐波那契数都是它前面两个斐波那契数之和，即 F2=F0+F1，F3=F1+F2，F4=F2+F3，以此类推

那么我们来看一下，如果我们要求斐波那契数列第N个数的值，那么我们有多少种求解的办法呢?

方式一：递归算法
方式二：记忆化搜索
方式三：动态规划的方案
方式四：动态规划(状态压缩)

斐波那契数列

509. 斐波那契数

递归求解

递归算法是一种基本的算法思想:

其基本思想是将一个大问题拆分成若干个相似的小问题
然后通过解决这些小问题来解决整个大问题

递归算法通常采用函数自身调用的方式实现，每次调用函数时都会处理一个规模更小的问题，直到问题规模足够小，可以直接求解为止

typescript

function fib(n: number): number {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

当 n 小于等于 1 时，直接返回 n; 否则，递归调用 fib 函数来计算 n-1 和 n-2 两个子问题的结果，然后将它们相加得到结果

递归函数必须有一个终止条件，以确保递归过程能够结束

记忆化搜索

对于递归算法，很容易出现重复计算的问题，因为在计算同一个子问题时，可能会被重复地计算多次

为了避免这个问题，我们可以使用记忆化搜索(Memoization)的技巧，将已经计算过的结果保存下来，以便在后续的计算中直接使用

typescript

function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n
  if (memo[n]) return memo[n]
  const res = fib(n - 1, memo) + fib(n - 2, memo)
  memo[n] = res
  return res
}

动态规划

从上面的斐波那契数列的例子中，我们可以发现，通过记忆化搜索的方式，可以避免重复计算，提高计算效率

而动态规划(Dynamic Programming)算法就是一种利用历史状态信息来避免重复计算的算法

动态规划算法可以看作是记忆化搜索的一种扩展，它通常采用自底向上的方式计算子问题的结果，并将结果保存下来以便后续的计算使用
在动态规划算法中，通常需要明确定义状态、设计状态转移方程、初始化状态，以及确定计算顺序等

下面我们可以以斐波那契数列为例，介绍如何用动态规划算法来解决这个问题:

需要注意的是，在动态规划算法中，为了保证状态之间的依赖关系正确，通常需要按照一定的计算顺序来计算子问题的结果
对于斐波那契数列问题来说，我们采用自底向上的方式计算子问题的结果，确保 dp[i-1] 和 dp[i-2] 的值已经计算出来了，才能计算 dp[i] 的值

typescript

function fib(n: number): number {
  // 1.定义状态
  // dp保留斐波那契数列中每一个位置对应的值(状态)
  // dp[x]表示的就是x位置对应的值(状态)

  // 2.状态转移方程: dp[i] = dp[i-1] + dp[i-2]
  // 状态转移方程一般情况都是写在循环(for/while)中

  // 3.设置初始化状态: dp[0]/dp[1]初始化状态
  const dp: number[] = [0, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  // 4.计算最终的结果
  return dp[n]
}

动态规划(状态压缩)

在动态规划算法中，有一种常见的优化方法叫做状态压缩，可以将状态的存储空间从数组优化为一个常数

对于斐波那契数列问题来说，我们只需要保存 dp[i-1] 和 dp[i-2] 两个状态的值，就能够计算出 dp[i] 的值，因此可以使用两个变量来存储这两个状态的值，从而实现状态压缩的优化

以下是使用状态压缩优化后的代码:

typescript

function fib(n: number): number {
  if (n <= 1) return n
  // 1.定义状态和初始化状态
  let perv = 0
  let cur = 1
  // 2.状态转移方程(状态压缩)
  for (let i = 2; i <= n; i++) {
    const newVal = perv + cur
    perv = cur
    cur = newVal
  }
  // 3.计算最终的结果
  return cur
}

爬楼梯(跳台阶)

70. 爬楼梯

爬楼梯(或者称之为跳台阶，我个人一直叫跳台阶)是一道经典的动态规划题目，也是面试常考的一道题目

爬楼梯：假设你正在爬楼梯。需要 n 阶你才能到达楼顶

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

跳台阶：假设有 n 级台阶，每次可以跳 1 级或 2 级台阶，问有多少种不同的跳法可以跳到第 n 级台阶

题目解析：

跳台阶问题是一道经典的动态规划问题，其本质是要求出到达第 n 级台阶的跳法数量
而到达第n级台阶只能由第 n-1 级台阶或第 n-2 级台阶跳上来，因此需要借助动态规划算法进行求解
通过引入状态、设计状态转移方程、初始化状态等方法，可以高效地求解跳台阶问题，

这道题目我们依然采用不同的方案来实现，让大家体会到动态规划的好处:

方式一：暴力递归
方式二：记忆化搜索
方式三：动态规划
方式四：状态压缩

暴力递归

我们可以先从暴力递归的方式开始，分析问题的本质，然后再逐步引入动态规划算法进行优化

对于跳台阶问题，假设有 n 级台阶，我们要求出到达第 n 级台阶的不同跳法数量

可以发现，从第 n 级台阶只能由第 n-1 级台阶或第 n-2 级台阶跳上来
因此，到达第 n 级台阶的跳法数量等于到达第 n-1 级台阶的跳法数量加上到达第 n-2 级台阶的跳法数量
即: jump(n) = jump(n-1) + jump(n-2)
对于 n=0 和 n=1 的情况，跳法数量分别为 1 和 1

typescript

function jump(n: number): number {
  if (n <= 1) return n
  return jump(n - 1) + jump(n - 2)
}

记忆化搜索

在介绍完暴力递归之后，我们可以引入记忆化搜索(Memoization)的方式进行优化

对于跳台阶问题，我们可以使用一个长度为 n+1 的数组 memo，用来记录每个阶梯的跳法数量
初始时，我们将 memo 数组中所有元素都初始化为 0
然后在递归过程中，如果 memo[n] 已经被计算过，直接返回 memo[n]
否则计算 memo[n] 的值，并将其存储到 memo[n] 中

typescript

function jump(n: number): number {
  const memo = new Array(n + 1).fill(0)
  return jumpMemo(n, memo)
}
function jumpMemo(n: number, memo: number[]): number {
  if (n <= 1) return n
  if (memo[n] !== 0) return memo[n]
  memo[n] = jumpMemo(n - 1, memo) + jumpMemo(n - 2, memo)
  return memo[n]
}

动态规划

我们可以使用一个一维数组来记录跳台阶的结果。

我们可以定义一个长度为 n+1 的一维数组 dp，用来记录每个阶梯的跳法数量

初始时，我们将 dp 数组中所有元素都初始化为 0
然后设置 dp[0]=1，dp[1]=1，表示到达第 0 级台阶和第 1 级台阶时，只有 1 种跳法
接下来，我们可以使用循环，依次计算 dp[2]、dp[3]、…、dp[n] 的值，最终得到 dp[n] 即为答案

typescript

function jump(n: number): number {
  const dp: number[] = [1, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

滑动窗口

另外一种常见的优化方法是滚动数组(滑动窗口)的方式。滚动数组的基本思想是：

由于每个状态只与它之前的状态有关
因此我们不需要记录所有的状态，只需要记录当前状态和它之前的若干个状态即可
通过不断更新这个滚动窗口，可以避免使用额外的空间，将空间复杂度进一步降低

typescript

function jump(n: number): number {
  let pre = 1
  let cur = 1
  for (let i = 2; i <= n; i++) {
    const iValue = pre + cur
    pre = cur
    cur = iValue
  }
  return cur
}

使用滚动数组的方式，可以将算法的空间复杂度降到 O(1)，是一种非常高效的动态规划优化方式

买卖股票最佳时机

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第i个元素 prices[i] 表示一支给定股票第i天的价格

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

动态规划

定义状态：设 dp[i] 表示前 i 天中能够获取的最大利润

状态转移方程:

对于第 i 天，有两种情况：
1. 在第 i 天卖出股票，在第 i 天的价格减去之前最便宜那天的买入价格，因此可以得到利润为 prices[i] - minPrice
2. 在第 i 天不卖出股票，那么目前的最大利润依然是前一天的最大利润 dp[i-1]
可以得到状态转移方程为：dp[i]=max(dp[i-1], prices[i]- minPrice)

初始状态：由于最小的天数是 1，因此初始状态为 dp[0]=0

typescript

function maxProfit(prices: number[]): number {
  const n = prices.length
  if (n <= 1) return 0
  // 1.定义状态dp[i]
  const dp: number[] = []
  // 2.设置初始化值
  dp[0] = 0
  // 3.状态转移方程dp[i]
  let minPrice = prices[0]
  for (let i = 1; i < n; i++) {
    dp[i] = prices[i] - minPrice
    minPrice = Math.min(prices[i], minPrice)
  }
  return Math.max(...dp)
}

这里使用了 Math.max 去遍历一遍了数组其实没有必要，稍微改写一下

typescript

function maxProfit(prices: number[]): number {
  const n = prices.length
  if (n <= 1) return 0
  const dp: number[] = []
  dp[0] = 0
  let minPrice = prices[0]
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], prices[i] - minPrice)
    minPrice = Math.min(prices[i], minPrice)
  }
  return dp[n - 1]
}

状态压缩

对于这个问题，实际上可以进行状态压缩

由于在状态转移方程中，当前状态只与前一个状态有关，因此可以不用维护整个 dp 数组，只需要用一个变量来表示前一个状态的最大利润即可

typescript

function maxProfit(prices: number[]): number {
  const n = prices.length
  if (n <= 1) return 0
  let preValue = 0
  let minPrice = prices[0]
  for (let i = 1; i < n; i++) {
    // 这里可以压缩的原因：i位置的值只和前一个位置有关系
    preValue = Math.max(preValue, prices[i] - minPrice)
    minPrice = Math.min(prices[i], minPrice)
  }
  return preValue
}

最大子数组和

53. 最大子数组和

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

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

动态规划

动态规划的规律:

以每个位置结尾的最大子序列的计算方式：
- 如果前面的子序列是负数，那么最大子序列和一定是自己
- 如果前面的子序列是正数，那么最大子序列和是自己+前值
由此可以得出计算公式：
- dp[i]= max(dp[i-1]+ nums[i], nums[i])
初始化值：dp[0]=nums[0]
计算最终值：找出所有值中最大的值即可

typescript

function maxSubArray(nums: number[]): number {
  const n = nums.length
  // 1.定义状态dp[i]
  const dp: number[] = []
  // 2.初始化状态
  dp[0] = nums[0]
  // 3.状态转移方程
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
  }
  return Math.max(...dp)
}

状态压缩

在动态规划算法中，我们需要定义一个一维数组 dp，其中 dp[i] 表示以第i个元素结尾的子数组的最大和

根据动态转移方程 dp[i]=max(dp[i-1]+nums[i],nums[i])我们可以计算出 dp 数组中的每个元素，从而求解原问题
这个算法的空间复杂度为 O(n)

然而，我们可以发现，dp 数组中的每个元素只与前一个元素有关

因此，我们可以使用滚动数组的技巧，将一维数组 dp压缩成一个变量 maxsum，从而将空间复杂度优化为O(1)。

typescript

function maxSubArray(nums: number[]): number {
  const n = nums.length
  let preValue = nums[0]
  let max = preValue
  for (let i = 1; i < n; i++) {
    preValue = Math.max(nums[i], nums[i] + preValue)
    max = Math.max(preValue, max)
  }
  return max
}

不同路径

62. 不同路径

一个机器人位于一个mxn网格的左上角(起始点在下图中标记为"start")

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标为"Finish")

问总共有多少条不同的路径?

动态规划

这个题目和跳楼梯其实是一类题目

设 dp[i][j] 表示从起点到网格的(i,j) 点的不同路径数

对于每个格子，由于机器人只能从上面或左边到达该格子，因此有以下两种情况：

从上面的格子到达该格子，即 dp[i][j]=dp[i-1][j]
从左边的格子到达该格子，即 dp[i][j]=dp[i][j-1]
- 因此，到达网格的(i,j)点的不同路径数就等于到达上面格子的路径数加上到达左边格子的路径数
- 动态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]
初始状态：对于边界情况，起点的路径数为1，即 dp[0][0]=1
计算最终状态：dp[m-1][n-1]

动态规划 ​

认识动态规划 ​

斐波那契数列 ​

递归求解 ​

记忆化搜索 ​

动态规划 ​

动态规划(状态压缩) ​

爬楼梯(跳台阶) ​

暴力递归 ​

记忆化搜索 ​

动态规划 ​

滑动窗口 ​

买卖股票最佳时机 ​

动态规划 ​

状态压缩 ​

最大子数组和 ​

动态规划 ​

状态压缩 ​

不同路径 ​

动态规划 ​

动态规划

认识动态规划

斐波那契数列

递归求解

记忆化搜索

动态规划

动态规划(状态压缩)

爬楼梯(跳台阶)

暴力递归

记忆化搜索

动态规划

滑动窗口

买卖股票最佳时机

动态规划

状态压缩

最大子数组和

动态规划

状态压缩

不同路径

动态规划