> For the complete documentation index, see [llms.txt](https://xyy94813.gitbook.io/x-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xyy94813.gitbook.io/x-note/ji-chu-suan-fa/dynamic-programming.md).

# 动态规划

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

> Programming 指的是一种表格法

## 基本思想

动态规划算法通常用于求解满足 **最优子结构（optimal substructure）** 的问题：问题的最优解由相关子问题的最优解组合而成。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

**与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。**

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 通过缓存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

**即，空间换时间**

不管子问题以后是否被用到，只要它被计算过，就将其缓存。

## 分类

动态规划一般分为：

* 线性动规
* 区域动规
* 树形动规
* 背包动规

## 动态规划的应用

四个步骤采用动态规划解决问题：

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

使用动态规划动重点在于列出问题的状态转移方程。

### 斐波那契数列

**斐波那契数列（Fibonacci sequence）**，又称黄金分割数列。

```
F(1)=1
F(2)=1
F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
```

使用递归求斐波那契数列：

```js
function fibonacci(n) {
  if (n <= 2) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}
```

采用自底向上的动态规划求解：

```js
function fibonacci(n) {
  const dp = [1, 1]; // f(1), f(2)

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

  return dp[n - 1];
}
```

### 钢条切割问题

## 参考

[五大基本算法之动态规划算法 DP](https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp)