# 动态规划

## 算法思想

* 有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串等等等。这就是规律，因为动态规划本身就是运筹学里的一种求最值的算法。
* 关键是明确【状态】和【选择】，列出【状态转移方程】
  * 明确 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];
}
```

## 优化

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://voyz.gitbook.io/voyz-algorithm/gui-na-zong-jie/dong-tai-gui-hua.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.