动态规划之三步问题

偏执的太偏执、 2024-03-16 21:31 68阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [三步问题][Link 1]  
![image.png][]  
根据题中的实力我们来分析, n = 3 时也就是到第 3 个台阶上, 为什么一共有 4 中方法可以上楼梯.  
**首先需要确定一点的是, 0 位置处表示所在的水平线它一共有 0 种方法可以上, 因为本身就在这个位置上.**  
**其次, 结果可能很大, 需要对结果取模 MOD = 1e9 + 7. 这里的 1e9 中 e 表示 10 的幂. 最终为 1 \* 10 ^ 9**  
从 0 位置开始到 1 位置, 一共只有 1 种方法, 也就是跨一步  
![image.png][image.png 1]  
从 0 位置开始到 2 位置, 一共有 2 种方法. 一步到 1 在一步到 2, 或者直接到 2.  
![image.png][image.png 2]  
从 0 位置开始到 3 位置, 一共有 3 种方法.

*  一直走一步, 先到 1 在到 2 最后到 3
 *  先走 1 步到 1. 在走 2 步到 3
 *  先走 2 步到 2, 在走 1 步到 3
 *  直接走 3 步到 3

![image.png][image.png 3]  
从 0 位置到达 4 位置, 由于一次最大只能跨 3 步, 因此最多一次也只能到 3 位置, 因此想要到达 4 必须在前面的 1 2 3 其中一个位置中转一下.

*  先到 1 中转, 从 0 先到 1 的过程一共有 1 种方法.

![image.png][image.png 4]

*  先到 2 中转, 从 0 到 2 的过程一共有 2 种方法 **( 如果不是直接从 0 到 2 算, 而是算上 0 -> 1 -> 2 后开始, 则会和第一种先到 1 中转中的其中一种情况重复, 特别需要注意 ! )**

![image.png][image.png 5]

*  先到 3 中转, 从 0 到 3 的过程一共有 3 种方法

![image.png][image.png 6]  
现在可以发现规律了嘛 ?**是不是有点像我们之前学的泰波那锲数, 也就是第 n 个台阶的跳法为前面 n - 1, n - 2, n - 3 这三个台阶跳法之和**

## 2. 状态表示 ##

以 i 位置为结尾, 表示为从 0 上到第 i 个台阶时一共有几种方法.  
**定义一个一维 dp 表 int\[\] dp = new int\[n + 1\], 其中 dp\[i\] 就表示从 0 上到第 i 个位置是对应的有几种方法**. 同样的, 其中 dp 的大小之所以为 n + 1 是因为我们要访问的是第 n 个台阶的跳发, dp 数组大小为 n + 1 时, 才能通过 dp 表获取.

## 3. 状态转移方程 ##

通过对题目分析的时候我们就发现了, 从 0 到 4 位置时的跳法等于前面 0 -> 1, 0 -> 2, 0 -> 3 的跳法之和. 对应到我们的转态表示中则为 :  
**dp\[i\] = dp\[i - 1\] + dp\[i - 2\] + dp\[i - 3\]**

## 4. 初始化 ##

初始化是为了防止 dp 数组的越界. 当不对前面几个数进行初始化时, 例如计算 dp\[2\] = dp\[1\] + dp\[0\] + dp\[-1\], 这肯定是非法越界了的. 因此我们是需要对前面几个较小的数 0, 1, 2 这三个台阶的方法数在 dp 表中进行初始化  
根据题目, 可以很容易知道 dp\[0\] = 0, dp\[1\] = 1, dp\[2\] = 2, dp\[3\] = 4.

## 5. 填表顺序 ##

此处, 可以知道想要计算 dp\[3\] 就必须先计算 dp\[0\], dp\[1\], dp\[2\]. 因此可以确定填写 dp 表的顺序为从左往右

## 6. 返回值 ##

根据题目要求, 返回的是从 0 到第 n 个台阶一共有几种方法. 联系到我们的状态表示中, 也就是 dp\[n\] 的值, 表示从 0 到第 n 个台阶一共有几种方法. 因此返回值为 dp\[n\]

## 7. 代码演示 ##

class Solution {
        
        public int waysToStep(int n) {
        
    
            int MOD = (int)1e9 + 7;
            // 边界值处理, 由于 n 的范围在[1, 1000000]之间.
            // 当 n 为 1 时, int[2], int[3] 的初始化就会越界.需要单独处理
            if(n == 1 || n == 2 ) 
                return n;
    
            if(n == 3) 
                return 4;
    
            // 1. 创建 dp 表
            int[] dp = new int[n + 1];
        
            // 2. 初始化
            dp[0] = 0; 
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            // 3. 填写 dp 表
            for(int i = 4; i <= n; i++) {
        
                // 由于结果很大, 每次相加操作都需要进行取模
                dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
            }
    
            // 4. 确认返回值
            return dp[n]; 
        }
    }

[Link 1]: https://leetcode.cn/problems/three-steps-problem-lcci/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5a989a728efb470382c6e35e61966bd6.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/db71a7399a7a49be9259e6b316fb6c0e.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/da88412cdfa545a2a8a0a2c1453cd256.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/36e9f70446854bc08d8b2e811af73bc1.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6550db9d8683463cb673697c93cb0904.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5113e04e3ba941cf8671a3c4eadf1c3b.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/64a581e352c0471aa6693ff6fc34c935.png