> For the complete documentation index, see [llms.txt](https://voyz.gitbook.io/voyz-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://voyz.gitbook.io/voyz-algorithm/gui-na-zong-jie/dong-tai-gui-hua.md).

# 动态规划

## 算法思想

* 有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串等等等。这就是规律，因为动态规划本身就是运筹学里的一种求最值的算法。
* 关键是明确【状态】和【选择】，列出【状态转移方程】
  * 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
  * **状态**：变化的量 （也就是原问题和子问题中会变化的变量）
  * **选择**：前后状态间的可选项 （也就是导致「状态」产生变化的行为）
  * **状态转移方程**：
    * dp\[状态1]\[状态2]… = dp\[状态1(变化)]\[状态2]…(选择1) + dp\[状态1(变化)]\[状态2]…(选择2) + ...
    * base case：dp\[0]\[0] = … ...

## 算法框架

```javascript
function dp(){ 
    // 创建dp table
    const dp = new Array(n+1).fill(new Array(m+1)...);

    // base case
    dp[0][…] = …

    // 填充dp table
    for(){
        for(){
            …
            dp[][] = ...
        }
    }

    return dp[m][n];
}
```

## 优化

* 状态压缩：如果当前状态只和前一次状态有关，则用两变量存这两次的状态即可