动态规划——斐波那契问题（Java）

╰半夏微凉° 2024-04-25 08:45 106阅读 0赞

**目录**

什么是动态规划？

练习

练习1：斐波那契数

练习2：三步问题

练习3：使用最小花费爬楼梯

练习4：解码方法

--------------------

## 什么是动态规划？ ##

**动态规划（Dynamic Programming，DP）：**是一种常见的算法设计技巧，通常用于解决**具有重叠子问题和最优子结构**的问题。在动态规划中，**将原问题分解成若干子问题**，通过**求解子问题的最优解**来得到原问题的最优解。

> **如何用动态规划解决问题？**

我们可以通过一下5步来解决动态规划问题

**1. 确定状态表示**

> 什么是状态表示？

**状态表示：**指在解决问题时所需要考虑和记录的关键信息。这些状态可以是问题的某种属性或特征，通过对这些状态的定义和记录，可以更好地理解问题的结构，从而设计出高效的动态规划算法。

在解决动态规划问题时，我们通常需要创建动态规划数组（dp），用于存储子问题的解，动态规划数组一般是一个 一维 或 二维 数组，而状态表示，可以理解为 dp表中值的含义 （即dp\[i\] 或 dp\[i\]\[j\]的含义）

> 如何确定状态表示？

1. 从题目要求中确定

2. 根据题目要求 以及 经验 确定

3. 在分析问题的过程中，发现重复子问题，从而确定状态表示

在使用动态规划解决问题时，我们常见的状态表示有两种：

> dp\[i\]：表示以i位置为结尾，...
> 
> dp\[i\]：表示以i位置为起始，...

**2. 确定状态转移方程**

> 什么是状态转移方程？

**状态转移方程**：确定状态之间的转移关系，即如何从一个状态推导出另一个状态。这是动态规划问题的核心，也是最难的一步，也就是需要确定 dp\[i\] 或 dp\[i\]\[j\] = ?

> 如何确定状态转移方程？

需要根据题目要求以及状态表示进行推导

**3. 进行初始化**

**初始化：**初始化动态规划数组或表格，通常需要设置起始状态的初始值，为后续的状态转移做准备。（例如：保证后续填表过程中不会发生越界）

**4. 确定填表顺序**

**5. 确定返回值**

接下来，我们通过动态规划来解决斐波那契相关练习，帮助我们进一步理解动态规划

## 练习 ##

### 练习1：斐波那契数 ###

**题目链接：**

[LCR 126. 斐波那契数 - 力扣（LeetCode）][LCR 126. _ - _LeetCode]

**题目描述：**

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

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

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

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

**示例 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 <= 100`

**思路分析：**

首先，我们来确定**状态表示** ，即dp\[i\] 表示什么

这道题根据题目要求就可直接定义出状态表示：dp\[i\]：第i个斐波那契数

确定了状态表示后，我们来**推导状态转移方程**，即dp\[i\] = ?

题目中其实已经告诉了我们状态转移方程，即 F(n) = F(n - 1) + F(n - 2)

因此，状态转移方程为：

**dp\[i\] = dp\[i-1\] + dp\[i - 2\]**

接下来，我们对dp数组进行**初始化：**

从递推公式我们就可以看出：在i = 0 和 i = 1时是没办法进行推导的，因为dp\[-2\] 和 dp\[-1\] 不存在

因此，我们在进行填表之前，要先将 0，1位置的值进行初始化，题目中已经告诉我们dp\[0\] = 0，dp\[1\] = 1

**填表顺序：**从左到右依次填写

**返回值：**要求出第n个斐波那契数，因此，返回值为dp\[n\]

**注意：题目要求答案需要取模 1e9+7(1000000007) ，不要忽略了这个条件**

**代码实现：**

class Solution {
        public int fib(int n) {
            //处理特殊情况
            if(n == 0) return 0;
            //创建dp表
            int[] dp = new int[n+1];
            //初始化
            dp[0] = 0;
            dp[1] = 1;
            //填表
            for(int i = 2; i <= n; i++){
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
            }
            //返回结果
            return dp[n];
        }
    }

**优化：**

在这道题中，我们可以使用**滚动数组**进行优化：

由于我们每次确定dp\[i\]时，只会涉及到三个变量：dp\[i-2\] dp\[i-1\] dp\[i\]，因此，每次求dp\[i\] 时只需要知道dp\[i-1\] 和 dp\[i-2\]的值就可以了，我们可以使用变量 a b c来分别表示 dp\[i-2\] dp\[i-1\] dp\[i\]， c = a + b，这样我们仅需使用三个变量就可以遍历数组

![16334faf3100434aaf3d2420131c9745.jpeg][]

在每次求出c的值后，更新a和b的值（**注意先更新a的值（a = b），再更新b的值（b = c）**） 使其向后移动，从而确定下一个结果

**优化代码：**

class Solution {
        public int fib(int n) {
            //处理特殊情况
            if(n == 0) return 0;
            //优化
            int a = 0, b = 1, c = 1;
            for(int i = 2; i <= n; i++){
                c = (a + b) % 1000000007;
                //更新a和b
                a = b;
                b = c;
            }
            //返回结果
            return c;
        }
    }

### 练习2：三步问题 ###

**题目链接：**

[面试题 08.01. 三步问题 - 力扣（LeetCode）][08.01. _ - _LeetCode]

**题目描述：**

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

**示例1:**

输入：n = 3 
     输出：4
     说明: 有四种走法

**示例2:**

输入：n = 5
     输出：13

**提示:**

1.  n范围在\[1, 1000000\]之间

**思路分析：**

小孩每次可以上1阶、2阶或3阶台阶，我们首先来模拟小孩上台阶的过程：  
![dc163f9d3d4e4acdb03f247a3aceb7c2.jpeg][]

**状态表示：**

我们以 i 位置为结尾进行分析：

那么在这道题中，以i位置为结尾，则可表示为小孩到达第i阶台阶，

而dp\[i\]则可表示：**小孩到达第i阶台阶时，一共有dp\[i\]种上楼方式**

**状态转移方程：**

由于小孩一次可以上1阶、2阶或3阶台阶，因此，小孩可以从 第 i-3 或 i-2 或 i-1位置到达第i阶台阶

![cde7ce935baa48028cadea6eb8527e86.jpeg][]

由于dp\[i\]： 小孩到达第i阶台阶时，一共有dp\[i\]种上楼方式，因此，

dp\[i-1\]： 小孩到达第 i - 1阶台阶时，一共有dp\[i - 1\]种上楼方式，则从i-1位置到达i位置有dp\[i-1\]种上楼方式

同理，从i-2位置到达i位置有dp\[i-2\]种上楼方式，从i-3位置到达i位置有dp\[i-3\]种上楼方式

因此，**dp\[i\] = dp\[i-1\] + dp\[i-2\] + dp\[i-3\]**

**初始化：**

由于dp\[i\] = dp\[i-1\] + dp\[i-2\] + dp\[i-3\]，因此，在i = 0, i = 1 以及 i = 2时是没办法进行推导的，

因此我们需要在填表之前，对0，1，2位置的值进行初始化，

由于至少上一阶台阶，因此，我们选择从1位置开始初始化，根据分析：dp\[1\] = 1, dp\[2\] = 2, dp\[3\] = 4

**填表顺序：**

i位置的值是由 i-1、i-2和 i-3位置的值得到的，因此填表顺序为**从左向右**

**返回值：**

要求上到第n阶台阶的方式，因此我们返回dp\[n\]

**注意：**由于本题计算的结果可能很多，需要对结果进行取模，在计算时，将三个值先加起来再进行取模（(dp\[i-1\] + dp\[i-2\]+ dp\[i-3\]) % 1000000007）是不可取的（会报错），因此我们每计算一次（每两个数相加），就进行一次取模

**代码实现：**

class Solution {
        public int waysToStep(int n) {
            //处理特殊情况
            if(n == 1 || n == 2) return n;
            //创建dp表
            int[] dp = new int[n+1];
            //初始化
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            //填表
            for(int i = 4; i <= n; i++){
                dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 + dp[i-3]) % 1000000007;
            }
            //返回
            return dp[n];
        }
    }

与练习1相同，由于dp\[i\] = dp\[i-1\] + dp\[i-2\] + dp\[i-3\]，因此，本题也可以使用滚动数组进行优化：

class Solution {
        public int waysToStep(int n) {
            //处理特殊情况
            if(n == 1 || n == 2) return n;
            if(n == 3) return 4;
            //创建dp表
            //初始化
            int a = 1, b = 2, c = 4, d = 0;
            //填表
            for(int i = 4; i <= n; i++){
                d = ((a + b) % 1000000007 + c) % 1000000007;
                a = b;
                b = c;
                c = d;
            }
            //返回
            return d;
        }
    }

### 练习3：使用最小花费爬楼梯 ###

**题目链接：**

[746. 使用最小花费爬楼梯 - 力扣（LeetCode）][746. _ - _LeetCode]

**题目描述：**

给你一个整数数组 `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`

**思路分析：**

可以从0或者1位置开始爬楼梯，当爬到i位置时，需要支付cost\[i\]继续向上爬楼梯，可以爬到 i + 1 或 i + 2位置，最终求爬到顶楼的最小花费（**注意：顶楼在 cost.length 位置，而不是 cost.length - 1位置**）

**状态表示：**

我们以 i 位置为结尾进行分析：

那么在这道题中，以i位置为结尾，则可表示到达第i阶台阶，

而dp\[i\]则可表示：到达第i阶台阶时的最小花费

**状态转移方程：**

由于一次只能向上爬一个或两个台阶，因此，只能从i - 2位置 或 i - 1位置到达i位置

![39976329e0f041df92e07f61176bc48a.jpeg][]

由于dp\[i\]： 到达第i阶台阶时的最小花费，因此，

dp\[i-1\]： 到达第 i - 1阶台阶时，最小花费为dp\[i-1\]，则从i-1位置到达i位置的最小花费为 dp\[i-1\] + cost\[i-1\]

同理，从i-2位置到达i位置时最小花费为dp\[i-2\]，则从 i-2 位置到达i位置的最小花费为 dp\[i-2\] + cost\[i-2\]

要求到达第i阶台阶时的最小花费，则**dp\[i\] = min(dp\[i-1\] + cost\[i-1\], dp\[i-2\] + cost\[i-2\])**

**初始化：**

可以从0位置或1位置开始向上爬，因此dp\[0\] = dp\[1\] = 0

**填表顺序**：由于dp\[i\] = min(dp\[i-1\] + cost\[i-1\], dp\[i-2\] + cost\[i-2\])，填表顺序为**从左向右**

**返回值：**要求到达顶楼（cost.length）的最小花费，因此返回dp\[cost.length\]

**代码实现：**

class Solution {
        public int minCostClimbingStairs(int[] cost) {
           int n = cost.length;
           //创建dp表
           int[] dp = new int[n + 1];
           //填表
           for(int i = 2; i <= n; i++){
                dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
           }
           //返回
           return dp[n];
        }
    }

### 练习4：解码方法 ###

**题目链接：**

[91. 解码方法 - 力扣（LeetCode）][91. _ - _LeetCode]

**题目描述：**

一条包含字母 `A-Z` 的消息通过以下映射进行了 **编码** ：

'A' -> "1"
    'B' -> "2"
    ...
    'Z' -> "26"

要 **解码** 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，`"11106"` 可以映射为：

*  `"AAJF"` ，将消息分组为 `(1 1 10 6)`
 *  `"KJF"` ，将消息分组为 `(11 10 6)`

注意，消息不能分组为 `(1 11 06)` ，因为 `"06"` 不能映射为 `"F"` ，这是由于 `"6"` 和 `"06"` 在映射中并不等价。

给你一个只含数字的 **非空** 字符串 `s` ，请计算并返回 **解码** 方法的 **总数** 。

题目数据保证答案肯定是一个 **32 位** 的整数。

**示例 1：**

输入：s = "12"
    输出：2
    解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

**示例 2：**

输入：s = "226"
    输出：3
    解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

**示例 3：**

输入：s = "06"
    输出：0
    解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

**提示：**

*  `1 <= s.length <= 100`
 *  `s` 只包含数字，并且可能包含前导零。

**思路分析：**

对给定的数字字符串进行解码，1-26分别对应A-Z，且在解码时不能出现前导0（如05）

**状态表示：**

我们以 i 位置为结尾进行分析：

那么在这道题中，以i位置为结尾，则dp\[i\]则可表示：0 到 i 位置一共有dp\[i\]种解码方法

**状态转移方程：**

由于1 - 26 分别对应 A - Z，则一个字母只可能由一个字符或两个字符进行解码得到，因此，以i位置为结尾进行解码时，最后一个字母只可能由当前字母（s\[i\]）或当前字母和前一个字母（s\[i\] 和 是\[i-1\]）进行解码得到

由于dp\[i\]： 0 到 i 位置一共有dp\[i\]种解码方法，因此，

dp\[i-1\]： 0 到 i 位置一共有dp\[i\]种解码方法，若s\[i\]能够解码，则以i位置为结尾的字符串共有 dp\[i-1\]种解码方法，若s\[i\]不能解码，则解码方法为0

同理，dp\[i-2\]表示以 i - 2为结尾的字符串一共有dp\[i-2\]种解码方法，若s\[i\]和s\[i-1\]位置组成的数字能够解码，则以i位置为结尾的字符串共有 dp\[i-2\]种解码方法，否之，则解码方法为0

因此，

> 若s\[i\]解码成功（s\[i\] >= '1' && s\[i\] <= '9'），则dp\[i\] += dp\[i-1\]，否之，dp\[i\] += 0
> 
> 若s\[i\]和s\[i-1\]位置组成的数字解码成功，则 dp\[i\] += dp\[i-2\]，否之，dp\[i\] += 0

在判断s\[i\]和s\[i-1\]位置组成的数字是否解码成功时，我们可以**先将其转换为数字 n = (s\[i-1\] - '0') \* 10 + (s\[i\] - '0')，由于不能出现前导0，因此，若结果在 10 - 26区间内，则解码成功**，反之，则失败

**初始化：**

由于在确定i位置的值时需要 i - 1 和 i - 2位置上的值，因此，我们要先初始化i = 0和 i = 1位置上的值：

dp\[0\]：若 s\[0\] >= '1' && s\[0\] <= '9'，则dp\[0\] = 1，反之，dp\[0\] = 1

dp\[1\]：s\[1\] >= '1' && s\[1\] <= '9'，dp\[1\] += dp\[0\]，反之，dp\[1\] += 0

s\[0\] 和 s\[1\]结合后数字在\[10, 26\]区间内，则dp\[1\] += 1，反之，dp\[1\] += 0

我们可以发现：前两个位置的初始化方式与填写后续i位置时十分相似，都需要判断字符是否能够

正确解码，因此，我们可以在最前面**添加一个辅助节点**，来帮助我们进行初始化：

![9158d229963a4b829ca4cf342f3e02fa.jpeg][]

在本题中，添加辅助节点后，就只需要初始化dp\[1\]，若 s\[1\] >= '1' && s\[1\] <= '9'，则dp\[1\] += dp\[0\]

![15426e05d6e644e2ae7704fa3606b6d9.jpeg][]

在添加辅助节点时需要注意：

> 1. 辅助节点里的值要保证后续填表过程中不出错
> 
> 2. 下标的映射关系

添加辅助节点后dp表与s的映射关系变为了 dp\[i\] - s\[i-1\]，因此，我们在编写代码时要注意

当s\[0\]解码正确时，dp\[1\] += dp\[0\]，因此，dp\[0\]应初始化为 1

**填表顺序：**从左往右

**返回值：**dp\[n\]

**代码实现：**

class Solution {
        public int numDecodings(String ss) {
            char[] s = ss.toCharArray();
            int n = s.length;
           //创建dp表
           int[] dp = new int[n+1];
           //初始化
           dp[0] = 1;//保证后续填表正确
           if(s[0] > '0' && s[0] <= '9') dp[1] += dp[0];
           //填表
           for(int i = 2; i <= n; i++){
                int num = s[i-1] - '0';//注意下标的映射关系
                if(num > 0 && num <= 9) dp[i] += dp[i-1];
                num = (s[i-2] - '0') * 10 + s[i-1] - '0';
                if(num >= 10 && num <= 26) dp[i] += dp[i-2];
           }
           //返回
           return dp[n];
        }
    }

[LCR 126. _ - _LeetCode]: https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
[16334faf3100434aaf3d2420131c9745.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/55fa0512d8ce4a0699089ecd76e5159f.jpeg
[08.01. _ - _LeetCode]: https://leetcode.cn/problems/three-steps-problem-lcci/description/
[dc163f9d3d4e4acdb03f247a3aceb7c2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9a6f8566d11b40d291fd965d3741c289.jpeg
[cde7ce935baa48028cadea6eb8527e86.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/7f0a018679b14c8b87fe6e9f8e49f222.jpeg
[746. _ - _LeetCode]: https://leetcode.cn/problems/min-cost-climbing-stairs/description/
[39976329e0f041df92e07f61176bc48a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c0dd74c0850d464b9391d6b885519bc1.jpeg
[91. _ - _LeetCode]: https://leetcode.cn/problems/decode-ways/description/
[9158d229963a4b829ca4cf342f3e02fa.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0226de2f83854118893ea3f1fa382358.jpeg
[15426e05d6e644e2ae7704fa3606b6d9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3f6f52e22ff74c17bd792e9e9185c737.jpeg