跳到主要内容

动态规划

是一种将问题分解成若干子问题的算法设计。

通常，动态规划解决的问题具有两种重要性质:

最优子结构（Optimal Substructure）：

问题的最优解可以通过其子问题的最优解来构造。换句话说，问题的整体最优解可以由子问题的局部最优解递推而来。

重叠子问题（Overlapping Subproblems）：

问题的子问题往往不是独立的，多个子问题共享相同的子问题。在这种情况下，动态规划算法会对相同的子问题进行重复计算，因此为了避免重复计算，需要将子问题的结果保存起来，以备后续使用。

动态规划通常涉及填充一个表格（通常是二维数组）来存储子问题的解，从而避免重复计算。这种填充的过程通常是自底向上的，从最小的子问题开始，逐步构建出更大规模的问题的解。

解决步骤如下：

定义状态：

明确定义问题的状态。状态是问题的变量，它们描述了问题的局部解。

找到状态转移方程：

通过找到问题状态之间的关系，建立状态转移方程。这表示问题的当前状态如何从前一个状态转移而来。

初始化边界条件：

定义问题最小规模的状态，并为它们提供初始值。这是递归和动态规划的区别之一，动态规划是自底向上的，需要知道最小规模问题的解。

填充表格：

从最小规模的问题开始，按照状态转移方程逐步填充表格，直至填充到问题的实际规模。

提取最终解：

根据填充后的表格，提取问题的最终解。动态规划广泛应用于解决优化问题，例如最短路径问题、背包问题、字符串匹配问题等。理解动态规划需要一定的实践和经验，通过解决一些经典问题，逐渐培养对动态规划的直观感觉。

case: 爬楼梯

问题描述：

假设你正在爬楼梯，每次你可以爬 1 或 2 个台阶。问：爬到第 n 阶台阶有多少种不同的方式

解题步骤:

定义状态

定义状态 dp[i] 表示爬到第i阶台阶时，需要的爬法个数

找到状态转移方程

对于第i阶台阶，可以从第i-1阶走一步到达，或者从第i-2阶走两步到达。
状态转移方程: dp[i] = dp[i-1] + dp[i-2];

初始化边界条件

爬到第0阶和第1阶的方式，只有一种方法。
所以，dp[0]=dp[1]=1

填充表格

从最小规模的问题开始，按照状态转移方程逐步填充表格

i:      0 1 2 3 4 5  6  7  8  9 10
dp[i]:  1 1 2 3 5 8 13 21 34 55 89

提取最终解

最终解为 dp[n],表示爬到第n阶台阶的不同爬法数量

function climbStairs(n: number): number {
 let dp = [];
 dp[0] = 1;
 dp[1] = 1;

 for(let i = 2; i <= n; i++) {
   dp[i] = dp[i-1] + dp[i-2] // 状态转移方程
 }
 return dp[n]
}

climbStairs(5)

解决步骤如下：
case: 爬楼梯