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

# 动态规划

## :pencil2: 动态规划

### :paintbrush: 背景

从一道例题开始：[**Triangle**](https://leetcode-cn.com/problems/triangle/)

> 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

> 例如，给定三角形：

> ```
> [                        [
>      [2],                         [2]
>     [3,4],                       [3,4]
>    [6,5,7],                    [6,5,5,7]        (转换的二叉树)
>   [4,1,8,3]                [4,1,1,8,1,8,8,3]
> ]                        ]
>
> 搜索的路径是三角形转换而来二叉树的前序遍历。
>
> 自底向上方法中：当前的位置的最优值为它相邻的两个节点中的最优值
> ```

> 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

#### 方法一：`DFS`（遍历——回溯，分治）——暴力搜索

> 遍历和分治法都是暴力搜索，搜索的路径是三角形转换而来二叉树的前序遍历。

```cpp
// 分治法——借助上面转化的二叉树理解
int rMinimumTotal(vector<vector<int>>& triangle, int x, int y, int height){
    if(x == height){
        return 0;
    }
    return min(rMinimumTotal(triangle, x + 1, y, height), 
              rMinimumTotal(triangle, x + 1, y + 1, height)) + triangle[x][y];
}
int minimumTotal(vector<vector<int>>& triangle) {
    int height = triangle.size();
    return rMinimumTotal(triangle, 0, 0, height);
}
```

**方法二：记忆化搜索——优化 `DFS`，缓存已经被计算的值（空间换时间），本质上是动态规划**

动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划。

> 动态规划和 `DFS` 区别
>
> * 二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 `DFS`，就可以解决
> * 像 triangle 这种是有重复走的情况，**子问题是有交集**，所以可以用动态规划来解决
>
> **可以用二维数组，可以借助一维数组（长度为三角形的行数），也可以原地操作**

{% tabs %}
{% tab title="自底向上" %}

```cpp
// 自底向上
int minimumTotal(vector<vector<int>>& triangle) {
    vector<vector<int>> hash;
    vector<int> rHash;
    int len = triangle.size() - 1;
    for(int i = len;i >= 0; i--){
        for(int j = 0; j < i + 1;j++){
            if(i == len){
                rHash.push_back(triangle[i][j]);
            }else{ // hash[len-i-1][j + 1], hash[len-i-1][j]这就是相邻的节点的坐标
                rHash.push_back(min(hash[len - i - 1][j + 1], 
                        hash[len - i - 1][j]) + triangle[i][j]);
            }
        }
        hash.push_back(rHash);
        rHash.clear();
    }
    return hash[len][0];
}
```

{% endtab %}

{% tab title="自顶向下" %}

```cpp
int minimumTotal(vector<vector<int>>& triangle) {
    vector<vector<int>> hash;
    vector<int> rHash;
    rHash.push_back(triangle[0][0]);
    hash.push_back(rHash);
    rHash.clear();
    for(int i = 1;i < triangle.size(); i++){
        for(int j = 0; j < i + 1;j++){
            if(j == 0){
                rHash.push_back(hash[i - 1][j] + triangle[i][j]);
            }else if(j == i){
                rHash.push_back(hash[i - 1][j - 1] + triangle[i][j]);
            }else{
                rHash.push_back(min(hash[i - 1][j - 1], hash[i - 1][j]) 
                 + triangle[i][j]);
            }
        }
        hash.push_back(rHash);
        if(i < triangle.size() - 1)
            rHash.clear();
    }
    int tmp = rHash[0];
    for(int i = 1;i < rHash.size(); i++){
        if(tmp > rHash[i])
            tmp = rHash[i];
    }
    return tmp;
}
```

{% endtab %}
{% endtabs %}

### :paintbrush: 递归与动规的关系

递归是一种程序的实现方式：函数的自我调用。

动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归的方式来实现(Memorization Search)。

### :paintbrush: 使用场景

满足两个条件

* 满足以下条件之一
* * 求最大/最小值（Maximum/Minimum ）
  * 求是否可行（Yes/No ）
  * 求可行个数（Count(\*) ）
* 满足不能排序或者不能交换（Can not sort / swap ）

> 如题：[longest-consecutive-sequence](https://leetcode-cn.com/problems/longest-consecutive-sequence/) 位置可以交换，所以不用动态规划。

### :paintbrush: 四点要素

1. 状态 State ：存储小规模问题的结果
2. 方程 Function ：状态之间的联系，怎么通过小的状态，来算大的状态
3. 初始化 Initialization ：最极限的小状态是什么，起点
4. 答案 Answer ：最大的那个状态是什么，终点、

**动态规划的设计，其实就是利用最优子结构和重叠子问题性质对穷举法进行优化，通过将中间结果保存在数组中，实现用空间来换取时间交换，实现程序的快速运行。（动态规划求解时，一般都会转化为网格进行求解，而且因为是空间换时间（避免了子问题的重复计算），因此一般迭代求解）。**

### :paintbrush: 滚动数组

**滚动数组**是DP中的一种编程思想。简单的理解就是让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

## :pencil2: 常见四种类型

1. Matrix DP (10%)
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)

> 注意点
>
> * 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法

### :pen\_ballpoint: 矩阵类型（10%）

#### 1、[minimum-path-sum](https://leetcode-cn.com/problems/minimum-path-sum/)

给定一个包含非负整数的 *m* x *n* 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

$$
function: f\[x]\[y] = min(f\[x-1]\[y], f\[x]\[y-1]) + A\[x]\[y]
$$

```cpp
// 原地操作
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(i == 0 && j == 0){
                grid[i][j] = grid[i][j];
            }else if(i == 0 && j > 0){
                grid[i][j] = grid[i][j - 1] + grid[i][j];
            }else if(j == 0 && i > 0){
                grid[i][j] = grid[i - 1][j] + grid[i][j];
            }else{
                grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
    }
    return grid[m - 1][n - 1];
}
```

#### 2、[unique-paths](https://leetcode-cn.com/problems/unique-paths/)

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

$$
function: f\[x]\[y] = f\[x-1]\[y], f\[x]\[y-1]
$$

```cpp
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for(int i = 1;i < m;i++){
        for(int j = 1;j < n;j++){
            dp[j] = dp[j - 1] + dp[j];
        }
    }
    return dp[n - 1];
}
```

#### 3、[unique-paths-ii](https://leetcode-cn.com/problems/unique-paths-ii/)

&#x20;在上一道题的基础上增加障碍物，网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

```cpp
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if(obstacleGrid[0][0] == 1)
        return 0;
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    std::vector<int> dp(n, 0);
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(i == 0 && j == 0){
                dp[j] = 1;
            }else if(i == 0 && j > 0){  // 初始化
                if(obstacleGrid[i][j] == 1 || dp[j - 1] == 0){
                    dp[j] = 0;
                }else{
                    dp[j] = 1;
                }
            }else if(j == 0 && i > 0){
                if(obstacleGrid[i][j] == 1){
                    dp[j] = 0;
                }
            }else{
                if(obstacleGrid[i][j] == 1){
                    dp[j] = 0;
                }else{
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
    }
    return dp[n - 1];
}
```

### :pen\_ballpoint: 序列类型（40%）

#### 1、[climbing-stairs](https://leetcode-cn.com/problems/climbing-stairs/)

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

```cpp
int climbStairs(int n) {
    if(n == 1 || n == 2)
        return n;
    int x = 1, y = 2;
    for(int i = 2;i < n;i++){
        int tmp = x + y;
        x = y;
        y = tmp;
    }
    return y;
}
```

#### 2、[jump-game](https://leetcode-cn.com/problems/jump-game/)

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。

```cpp
bool canJump(vector<int>& nums) {
    int curr_end = 0;
    for(int i = 0;i < nums.size();i++){
        if(curr_end >= i){
            curr_end = curr_end > (i + nums[i]) ? curr_end : (i + nums[i]);
        }else{
            curr_end = -1;
            break;
        }
    }
    return curr_end == -1 ? false : true;
}
```

#### 3、[机器人达到指定位置方法数](https://www.nowcoder.com/questionTerminal/54679e44604f44d48d1bcadb1fe6eb61)

假设有排成一行的N个位置，记为1\~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对`1e9+7`取模。

{% tabs %}
{% tab title="状态穷举" %}

```cpp
const int prime = 1e9 + 7;

long long getSolutions(int n, int m, int k, int p) {
	vector<vector<long long>> solutions(k + 1, vector<long long>(n + 2));
	// base case
	for (int i = 0; i < n + 2; ++i) {
		solutions[0][i] = 0;
	}
	solutions[0][m] = 1;
	for (int i = 1; i < k + 1; ++i) {
		for (int j = 1; j < n + 1; ++j) {
			solutions[i][j] = solutions[i - 1][j - 1] + solutions[i - 1][j + 1];
			solutions[i][j] %= prime;
		}
	}
	return solutions[k][p];
}
```

{% endtab %}

{% tab title="优化" %}

```cpp
long long getSolutions(int n, int m, int k, int p) {
    vector<long long> curr(n + 2);
    vector<long long> last(n + 2);
    // base case
    for (int i = 0; i < n + 2; ++i) {
        last[i] = 0;
    }
    last[m] = 1;
    for (int i = 1; i < k + 1; ++i) {
        for (int j = 1; j < n + 1; ++j) {
            curr[j] = last[j - 1] + last[j + 1];
            curr[j] %= prime;
        }
        for (int j = 1; j < n + 1; ++j) {
            last[j] = curr[j];
        }
    }
    return curr[p];
}
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://mqjyl2012.gitbook.io/algorithm/algorithm-thinking/dynamic-programming-algorithm.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.