【动态规划】斐波那契数列模型

港控/mmm° 2024-03-18 00:36 29阅读 0赞

#### 文章目录 ####

*  动态规划（斐波那契数列模型）
 *   *  1. 第 N 个泰波那契数
     *  2. 三步问题
     *  3. 使用最小花费爬楼梯
     *  4. 解码方法

## 动态规划（斐波那契数列模型） ##

### 1. 第 N 个泰波那契数 ###

[题目链接][Link 1]

1.  状态表示
    
    `dp[i]`所表示的含义，那么这个状态表示怎么来的那？
    
    > 题目要求、经验根据题目要求、分析问题的过程中发现重复子问题
2.  状态转移方程
    
    dp\[i\]等于什么。根据这题的题目我们发现
    
    `d[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]`
3.  初始化
    
    保证填表的时候不越界
4.  填表顺序
    
    为了填写当前的状态，所需的状态已经完成了
5.  返回值
    
    这个题目的返回值当然就是`dp[n]`了

AC代码：

class Solution 
    {
        
    public:
        int tribonacci(int n) 
        {
        
            if (n == 0 || n == 1) return n;
            vector<int> dp(n + 1);
            dp[0] = 0, dp[1] = 1, dp[2] = 1;
            for (int i = 3; i <= n; i++)
            {
        
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            }
            return dp[n];
        }
    };

优化之后：

![7uvv2rdryg-1690091743374.png][]

AC代码：

class Solution 
    {
        
    public:
        int tribonacci(int n) 
        {
        
            if (n == 0) return 0;
            if (n == 1 || n == 2) return 1;
            int a = 0, b = 1, c = 1, d = 0;
            for (int i = 3; i <= n; i++)
            {
        
                d = a + b + c;
                a = b;
                b = c;
                c = d;
            }
            return d;
        }
    };

### 2. 三步问题 ###

[题目链接][Link 2]

1.  状态表示
    
    `dp[i]`表示：到达i位置时，一共有多少中走法
2.  状态转移方程
    
    ![28z3486cl8-1690092114378.png][] ![osc2lgkq0u-1690092473244.png][]
3.  初始化
4.  填表
5.  返回值

AC代码：

class Solution
    {
        
        const int mod = 1e9 + 7;
    public:
        int waysToStep(int n)
        {
        
            if (n == 1) return 1;
            if (n == 2) return 2;
            if (n == 3) return 4;
            vector<int> dp(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]) % mod + dp[i - 3]) % mod;
            }
            return dp[n];
        }
    };

这个题目三个值都加起来，再取模是不行的。这里我们没计算一次加法（乘法）都要进行一次取模运算

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

[题目链接][Link 3]

**解法一**

1.  状态表示
    
    `dp[i]`表示到达i位置的最小花费
2.  状态转移方程
    
    ![cx9or1nh7d-1690093775366.png][]
3.  初始化
4.  填表顺序
5.  返回值

AC代码：

class Solution 
    {
        
    public:
        int minCostClimbingStairs(vector<int>& cost) 
        {
        
            int len = cost.size();
            vector<int> dp(len + 1);
            for (int i = 2; i <= len; i++)
            {
        
                dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));
            }
            return dp[len];
        }
    };

**解法二**

1.  状态表示
    
    `dp[i]`从i位置出发，到达楼顶所需的最小花费
2.  状态转移方程
    
    ![ttr99vgcnr-1690111877257.png][]
3.  初始化
    
    `dp[n - 1] = cost[n - 1], dp[n - 2] = cont[n - 2]`
4.  填表
    
    从左往右
5.  返回值
    
    `min(dp[0], dp[1])`

AC代码：

class Solution 
    {
        
    public:
        int minCostClimbingStairs(vector<int>& cost) 
        {
        
            int n = cost.size();
            vector<int> dp(n);
            dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
            for (int i = n - 3; i >= 0; i--)
            {
        
                dp[i] = min((dp[i + 1] + cost[i]), (dp[i + 2] + cost[i]));
            }
            return min(dp[0], dp[1]);
        }
    };

### 4. 解码方法 ###

[题目链接][Link 4]

1.  状态表示
    
    以i位置为结尾，有多少种解码方法
2.  状态转移方程
    
    ![d2up6hdnto-1690112655369.png][]
3.  初始化
    
    `dp[0] = 1 或者0`
    
    `dp[1]`也有三种情况 0 、1 、2
4.  填表
5.  返回值

AC代码：

class Solution 
    {
        
    public:
        int numDecodings(string s) 
        {
        
            int n = s.size();
            vector<int> dp(n + 1);
            if (s[0] == '0') dp[0] = 0;
            else dp[0] = 1;
            if (n == 1) return dp[0];
            if (s[1] >= '1' && s[1] <= '9') dp[1] += dp[0];
            int t = (s[0] - '0') * 10 + s[1] - '0';
            if (t >= 10 && t <= 26) dp[1] += 1;
            for (int i = 2; i < n; i++)
            {
        
                if (s[i] >= '1' && s[i] <= '9') dp[i] += dp[i - 1];
                int t = (s[i - 1] - '0') * 10 + s[i] - '0';
                if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
            }
            return dp[n - 1];
        }
    };

还可以使用辅助节点的方式来处理这个题目的边界问题：

需要注意的是：

1.  辅助节点里面的值要保证后续填表是正确的
2.  下标的映射关系

[Link 1]: https://leetcode.cn/problems/n-th-tribonacci-number/
[7uvv2rdryg-1690091743374.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cacd037a6f1844bb84be07eff0b74229.png
[Link 2]: https://leetcode.cn/problems/three-steps-problem-lcci/
[28z3486cl8-1690092114378.png]: https://img.fswuyu.cn/zy-note-img/2023/7/28z3486cl8-1690092114378.png
[osc2lgkq0u-1690092473244.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fd7bcdfb067e40c79cd20c3ac2fde5b4.png
[Link 3]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[cx9or1nh7d-1690093775366.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/672808b57f79416c82da0903c4f573f2.png
[ttr99vgcnr-1690111877257.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ed492a9bff0a4b4b82664cd8f8ae0360.png
[Link 4]: https://leetcode.cn/problems/decode-ways/
[d2up6hdnto-1690112655369.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4fa664d3962c445e8065e28c612448c7.png