算法沉淀 —— 动态规划篇（斐波那契数列模型）

ゝ一纸荒年。 2024-04-06 15:50 85阅读 0赞

#### 算法沉淀 —— 动态规划篇（斐波那契数列模型） ####

*  前言
 *  一、第 N 个泰波那契数
 *  二、三步问题
 *  三、使用最小花费爬楼梯
 *  四、解码方法

## 前言 ##

几乎所有的动态规划问题大致可分为以下5个步骤，后续所有问题分析都将基于此

*  1.、状态表示：通常状态表示分为基本分为以下两种，其中更是以第一种为甚。
    
     *  `以i为结尾`，dp\[i\] 表示什么，通常为代求问题（具体依题目而定）
     *  `以i为开始`，dp\[i\]表示什么，通常为代求问题（具体依题目而定）
 *  2、状态转移方程  
    \*以上述的dp\[i\]意义为以i位置为分界， 通过`最近一步来分析和划分问题`，由此来得到一个有关dp\[i\]的状态转移方程。
 *  3、dp表创建，初始化
    
     *  动态规划问题中，如果直接使用状态转移方程通常会伴随着`越界访问`等风险，所以一般需要初始化。而初始化最重要的两个注意事项便是：`保证后续结果正确，不受初始值影响；下标的映射关系`。
     *  而`初始化一般分为以下两种：`
        
         *  `直接初始化开头的几个值。`
         *  `一维空间大小+1，下标从1开始；二维增加一行/一列`。
 *  4、填dp表、填表顺序：根据状态转移方程来确定填表顺序。
 *  5、确定返回值

## 一、第 N 个泰波那契数 ##

【题目链接】：[1137. 第 N 个泰波那契数][1137. _ N]  
【题目】：  
![在这里插入图片描述][9ec3d2fbf3f24ae48993f80e9eb20296.png]  
【分析】：  
 题目要第n个斐波那契数，我们令dp\[i\]表示第i个斐波那契数。题目中以及给出了状态转移方程:`dp[i] = dp[i-1] + dp[i-2] +dp[i-3]`。但我们发现当i为0、1、2时显然状态转移方程错误，还会越界访问。所以我们仅需将前3个元素特殊处理，然后在从下标2开始填dp表。最后返回结果即可！  
【代码实现】：

class Solution {
        
    public:
        int tribonacci(int n) {
        
            if(n == 0)
                return 0;
            else if(n == 1 || n == 2)
                return 1;
            //创建dp表
            vector<int> dp(n + 1);
            //初始化
            dp[0] = 0, dp[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];
        }
    };

## 二、三步问题 ##

【题目链接】：[面试题 08.01. 三步问题][08.01.]

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

【分析】：  
 我们可以定义dp\[i\]表示小孩走到i阶台阶时上楼方式的最大值。由题目可知，小孩一次可以走1阶、2阶、3阶。所以我们容易得到状态转移方程为`dp[i] = dp[i-1] + dp[i-2] + dp[i-3]`(题目明确表示结果肯过大，记得模1000000007！！)。  
 显然你以及观察到当i <=3时，状态转移方程不适应。所以我们可以提前将前3个dp表中的值进行初始化；然后在从左往右依次填表。最后返回结果即可！！

【代码实现】：

class Solution {
        
    public:
        int waysToStep(int n) {
        
            //特殊处理
            if(n == 1)
                return 1;
            else if(n == 2)
                return 2;
            else if(n == 3)
                return 4;
            const int DEL = 1000000007;
            vector<int> dp(n + 1);//创建dp表，多开一个空间，让下标对应
            //初始化
            dp[1] = 1, dp[2] = 2, dp[3] = 4;
            //填表
            for(int i = 4; i <= n; i++)
                dp[i] = (dp[i - 1] + (dp[i - 2] + dp[i - 3]) % DEL) % DEL;
            return dp[n];
        }
    };

## 三、使用最小花费爬楼梯 ##

【题目链接】：[746. 使用最小花费爬楼梯][746.]  
【题目】：  
 给你一个整数数组 cost ，其中 cost\[i\] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。  
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

实例：  
![在这里插入图片描述][1f7a17325e6b4cfa94df575a0dbe610c.png]

【分析】  
 我们可以用dp\[i\]变化到达下标为i的台阶时的最低花费。题目中指出，一步可选择向上爬一个或者两个台阶。所以dp\[i\]必然是从i-1阶或i-2阶台阶爬上来的，易得状态转移方程为`dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);`。  
 显然当i为0、1时需要单独处理（处理为0）。但C++vector创建dp表时，已经将所有数据初始化为0，所以此步不需要单独实现。然后就是从下标2开始，从左往右依次填dp表了。最后返回结果即可！！

【代码实现】：

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

## 四、解码方法 ##

【题目链接】：[91. 解码方法][91.]  
【题目】：  
一条包含字母 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位的整数。

【分析】：  
 我们定义dp\[i\]表示从下标\[0, i\]的子字符串的解法方式总数。显然解码到dp\[i\]的最近一步分为：从\[0,i-1\] 加s\[i\]，如果s\[i\]合法，此时d\[i\] += dp\[i-1\];从\[0, i-2\] 加s\[i-1,i\]，如果s\[i-1, i\]合法，此时dp\[i\] += dp\[i-2\]。所以我们可以得到对应的状态转移方程。（具体看代码）  
 显然我们需要将dp\[1\]、dp\[2\]单独处理，就不多说了。然后从左往右依次填表，最后返回结果！！  
![在这里插入图片描述][0f119b7ec5a7488d9255a146c3a2e8b6.png]

【代码实现】：

class Solution {
        
    public:
        int numDecodings(string s) {
        
            int n = s.size();
            //创建dp表
            vector<int> dp(n);
            //初始化
            dp[0] = s[0] != '0';
            if(n == 1)
                return dp[0];
            if(s[0] != '0' && s[1] != '0')
                dp[1]++;
            int tmp = (s[0] - '0') * 10 + s[1] - '0';
            if(tmp >= 10 && tmp <= 26)
                dp[1]++;
            //填表
            for(int i = 2; i < n; i++)
            {
        
                if(s[i] != '0')
                    dp[i] += dp[i - 1];
                int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';
                if(tmp >= 10 && tmp <= 26)
                    dp[i] += dp[i - 2] ;
            }
            return dp[n - 1];
        }
    };

[1137. _ N]: https://leetcode.cn/problems/n-th-tribonacci-number/description/
[9ec3d2fbf3f24ae48993f80e9eb20296.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/5bf82f18b8344d92a7b04dad365df79d.png
[08.01.]: https://leetcode.cn/problems/three-steps-problem-lcci/description/
[746.]: https://leetcode.cn/problems/min-cost-climbing-stairs/description/
[1f7a17325e6b4cfa94df575a0dbe610c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/77222f7b7ebc4abbbb43079a376de20a.png
[91.]: https://leetcode.cn/problems/decode-ways/description/
[0f119b7ec5a7488d9255a146c3a2e8b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b16a0147530e40bab3241e0820335021.png