动态规划-基础（斐波那契数、爬楼梯、使用最小花费爬楼梯、不同路径、不同路径II、整数拆分、不同的二叉搜索树）

快来打我* 2023-09-25 17:19 25阅读 0赞

> 动态规划，英文：Dynamic Programming，简称 **DP**，如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的。  
> **动态规划问题，五步走：**  
> 状态定义：确定 dp 数组，下标及其含义  
> 状态转移：  
> 初始化：  
> 遍历顺序：  
> 返回值：  
> **动态规划代码有问题分析**  
> 举例推导状态转移公式  
> 打印 dp 数组日志

## 1.斐波那契数 ##

**题目链接：**[509. 斐波那契数 - 力扣（LeetCode）][509. _ - _LeetCode]

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

**示例 1：**

> 输入：n = 2  
> 输出：1  
> 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

**示例 2：**

> 输入：n = 3  
> 输出：2  
> 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

**示例 3：**

> 输入：n = 4  
> 输出：3  
> 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

**提示：**

0 <= n <= 30

### 代码： ###

/**
        1. 状态定义：dp[i]为斐波那契数列的自变量i，dp[i] = F(i)
        2. 状态转移：dp[i] = dp[i-1] + dp[i-2]
        3. 初始化：dp[0] = 0, dp[1] = 1
        4. 遍历顺序：正序
        5. 返回形式：dp[n]
         */
        public int fib(int n) {
            if(n == 0 || n == 1) {
                return n;
            }
            int a = 0, b = 1,sum = 0;
            for(int i = 2; i <= n; i++) {
                sum = a + b;
                a = b;
                b = sum;
            }
            return sum;
        }

## 2. 爬楼梯 ##

**题目链接：**[70. 爬楼梯 - 力扣（LeetCode）][70. _ - _LeetCode]

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**示例 1：**

> 输入：n = 2  
> 输出：2  
> 解释：有两种方法可以爬到楼顶。  
> 1 阶 + 1 阶  
> 2 阶

**示例 2：**

> 输入：n = 3  
> 输出：3  
> 解释：有三种方法可以爬到楼顶。  
> 1 阶 + 1 阶 + 1 阶  
> 1 阶 + 2 阶  
> 2 阶 + 1 阶

**提示：**

1 <= n <= 45

### 思路： ###

![fcdfd8e846a06b7d3543fd33043e20da.png][]

### 代码： ###

/**
        1. 状态定义：到达第 i 个台阶，有 dp[i] 中方法
        2. 状态转移：dp[i] = dp[i-1] + dp[i-2]
        3. 初始化：dp[1] = 1 dp[2] = 2  注意题中要求 n ！= 0
        4. 遍历顺序：从前往后
        5. 返回值：返回 dp[n]
         */
        public int climbStairs(int n) {
            if(n < 2) return n;
            int[] dp = new int[n+1];
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <= n; i++) {
                dp[i] = dp[i-2] + dp[i-1];
            }
            return dp[n];
        }

## 3. 使用最小花费爬楼梯 ##

**题目链接：**[使用最小花费爬楼梯][Link 1]

给你一个整数数组 cost ，其中 cost\[i\] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

**示例 1：**

> 输入：cost = \[10,15,20\]  
> 输出：15  
> 解释：你将从下标为 1 的台阶开始。  
> 支付 15 ，向上爬两个台阶，到达楼梯顶部。  
> 总花费为 15 。

**示例 2：**

> 输入：cost = \[1,100,1,1,1,100,1,1,100,1\]  
> 输出：6  
> 解释：你将从下标为 0 的台阶开始。  
> 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。  
> 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。  
> 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。  
> 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。  
> 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。  
> 支付 1 ，向上爬一个台阶，到达楼梯顶部。  
> 总花费为 6 。

**提示：**

2 <= cost.length <= 1000

0 <= cost\[i\] <= 999

### 思路： ###

![81eb370e0728ffb7034bfc2ded3a27fc.png][]

### 代码： ###

/**
        1. 状态定义：到达 i 位置最小花费 dp[i]
        2. 状态转移：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        3. 初始化：dp[0] = 0, dp[1] = 0 前两个台阶是直接到达的，不花费
        4. 遍历顺序：从前往后
        5. 返回值：dp[cost.length]
         */
        public int minCostClimbingStairs(int[] cost) {
            int len = cost.length;
            int[] dp = new int[len + 1];
            dp[0] = 0;
            dp[1] = 0;
            for(int i = 2; i <= len; i++) {
                dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
            }
            return dp[len];
        }

## 4. 不同路径 ##

题目链接：[62. 不同路径 - 力扣（LeetCode）][62. _ - _LeetCode]

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

**示例 1：**

![80786aa22c6f4dcdf52139532bb9dc7d.png][]

> 输入：m = 3, n = 7  
> 输出：28

**示例 2：**

> 输入：m = 3, n = 2  
> 输出：3  
> 解释：  
> 从左上角开始，总共有 3 条路径可以到达右下角。  
> 向右 -> 向下 -> 向下  
> 向下 -> 向下 -> 向右  
> 向下 -> 向右 -> 向下

**示例 3：**

> 输入：m = 7, n = 3  
> 输出：28

**示例 4：**

> 输入：m = 3, n = 3  
> 输出：6

**提示：**

1 <= m, n <= 100

题目数据保证答案小于等于 2 \* 109

### 思路： ###

![d0ee8057b9ce91f1d26f896fd04cfb14.png][]

### 代码： ###

/**
     1. 状态定义：dp[i][j] 表示从 (0,0) 到 ()
     2. 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
     3. 初始化： 行：dp[0][j] = 1, 列：dp[i][0] = 1
     4. 遍历顺序：从左到右，从上到下
     5. 返回值：dp[m][n]
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 初始化
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        // 遍历打印
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

## 5. 不同路径 II ##

**题目链接：**[63. 不同路径 II - 力扣（LeetCode）][63. _ II - _LeetCode]

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

**示例 1：**

> 输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
> 输出：2  
> 解释：3x3 网格的正中间有一个障碍物。  
> 从左上角到右下角一共有 2 条不同的路径：  
> 向右 -> 向右 -> 向下 -> 向下  
> 向下 -> 向下 -> 向右 -> 向右

**示例 2：**

> 输入：obstacleGrid = \[\[0,1\],\[0,0\]\]  
> 输出：1

**提示：**

*  m == obstacleGrid.length

*  n == obstacleGrid\[i\].length

*  1 <= m, n <= 100

*  obstacleGrid\[i\]\[j\] 为 0 或 1

### 思路： ###

![197f8737a6094e8daf421aec7269e5ab.png][]

### 代码： ###

/**
        1. 状态定义： dp[i][j] 表示到达 (i,j) 位置有多少种走法
        2. 状态转移：条件：obs[i][j] = 0 时才有这个方程，表示这个位置没有障碍物
        dp[i][j] = dp[i-1][j] + dp[i][j-1]   
        3. 初始化：条件：当 obs[i][0] = 0 时，才有 dp[i][0] = 1
                        当 obs[0][j] = 0 时，才有 dp[0][j] = 1  
        4. 遍历顺序：从上到下，从左到右
        5. 返回值：当初始位置或结束位置 obs 为 1 时，表示有障碍，直接返回 0，正常情况下返回 dp[m][n]
         */
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length; // 行
            int n = obstacleGrid[0].length; // 列
            if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
                return 0;
            }
            int[][] dp = new int[m][n];
            // 初始化
            for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
                dp[i][0] = 1;
            }
            for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
                dp[0][j] = 1;
            }
            for(int i = 1; i < m; i++) {
                for(int j = 1; j < n; j++) {
                    if(obstacleGrid[i][j] == 0) {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
            return dp[m-1][n-1];
        }

## 6. 整数拆分 ##

**题目链接：**[343. 整数拆分 - 力扣（LeetCode）][343. _ - _LeetCode]

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

**示例 1:**

> 输入: n = 2  
> 输出: 1  
> 解释: 2 = 1 + 1, 1 × 1 = 1。

**示例 2:**

> 输入: n = 10  
> 输出: 36  
> 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

**提示:**

2 <= n <= 58

### 思路： ###

![b59a61d9b5279825705fba628eeb8f6c.png][]

### 代码： ###

/**
        1. 状态定义：对 i 进行拆分，得到最大的积为 dp[i]
        2. 状态转移：dp[i] = Math.max(dp[i], Math.max(j*(i-j), j * dp[i-j]));
        3. 初始化：dp[0] = 0,dp[1] = 0,dp[2] = 2
        4. 遍历顺序：从前向后
        5. 返回值：dp[n]
         */
        public int integerBreak(int n) {
            int[] dp = new int[n+1];
            dp[2] = 1;
            for(int i = 3; i <= n; i++) {
                for(int j = 1; j <= i-j; j++) {
                    dp[i] = Math.max(dp[i],Math.max(j*(i-j), j*dp[i-j]));
                }
            }
            return dp[n];
        }

## 7. 不同的二叉搜索树 ##

**题目链接：**[96. 不同的二叉搜索树 - 力扣（LeetCode）][96. _ - _LeetCode]

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

**示例 1：**

![Image 1][]

输入：n = 3

输出：5

**示例 2：**

输入：n = 1

输出：1

**提示：**

1 <= n <= 19

### 思路： ###

![841608e66a9caedf7c47e6e83786152e.png][]

### 代码： ###

/**
     1. 状态定义：dp[i] 表示输入 i，有 dp[i] 种不同的二叉搜索树
     2. 状态转移：dp[i] += dp[j-1]*dp[i-j]
     3. 初始化：dp[0] = 1, dp[1] = 1
     4. 遍历顺序：从小到大
     5. 返回值：dp[n]
    */
    public int numTrees(int n) {
     int[] dp = new int[n+1];
     dp[0] = 1;
     dp[1] = 1;
     for(int i = 2; i <= n; i++) {
         for(int j = 1; j <= i; j++) {
             dp[i] += dp[j-1]*dp[i-j];
         }
     }
     return dp[n];
    }2. 背包问题

[509. _ - _LeetCode]: https://leetcode.cn/problems/fibonacci-number/
[70. _ - _LeetCode]: https://leetcode.cn/problems/climbing-stairs/
[fcdfd8e846a06b7d3543fd33043e20da.png]: https://img-blog.csdnimg.cn/img_convert/fcdfd8e846a06b7d3543fd33043e20da.png
[Link 1]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[81eb370e0728ffb7034bfc2ded3a27fc.png]: https://img-blog.csdnimg.cn/img_convert/81eb370e0728ffb7034bfc2ded3a27fc.png
[62. _ - _LeetCode]: https://leetcode.cn/problems/unique-paths/
[80786aa22c6f4dcdf52139532bb9dc7d.png]: https://img-blog.csdnimg.cn/img_convert/80786aa22c6f4dcdf52139532bb9dc7d.png
[d0ee8057b9ce91f1d26f896fd04cfb14.png]: https://img-blog.csdnimg.cn/img_convert/d0ee8057b9ce91f1d26f896fd04cfb14.png
[63. _ II - _LeetCode]: https://leetcode.cn/problems/unique-paths-ii/
[197f8737a6094e8daf421aec7269e5ab.png]: https://img-blog.csdnimg.cn/img_convert/197f8737a6094e8daf421aec7269e5ab.png
[343. _ - _LeetCode]: https://leetcode.cn/problems/integer-break/
[b59a61d9b5279825705fba628eeb8f6c.png]: https://img-blog.csdnimg.cn/img_convert/b59a61d9b5279825705fba628eeb8f6c.png
[96. _ - _LeetCode]: https://leetcode.cn/problems/unique-binary-search-trees/
[Image 1]: 
[841608e66a9caedf7c47e6e83786152e.png]: https://img-blog.csdnimg.cn/img_convert/841608e66a9caedf7c47e6e83786152e.png