【算法】DP系列之 斐波那契数列模型

【ps】本篇有 4 道 leetcode OJ。  

目录

一、算法简介

二、相关例题

1）第 N 个泰波那契数

.1- 题目解析

.2- 代码编写

2）三步问题

.1- 题目解析

.2- 代码编写

3）使用最小花费爬楼梯

.1- 题目解析

.2- 代码编写

4）解码方法

.1- 题目解析

.2- 代码编写

---

一、算法简介

        动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

        动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

        与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上）。

【Tips】动态规划算法解决问题的分类

• 计数：有多少种方式走到右下角 / 有多少种方法选出k个数使得和是 sum。
• 求最大值/最小值：从左上角走到右下角路径的最大数字和最长上升子序列长度。
• 求存在性：取石子游戏，先手是否必胜 / 能不能取出 k 个数字使得和是 sum。

【Tips】动态规划dp算法一般步骤

1. 确定状态表示（dp[ i ] 的含义是什么，来源：1、题目要求；2、经验+题目要求；3、分析问题时发现重复子问题）
2. 状态转移方程（可求得 dp[ i ] 的数学公式，来源：题目要求+状态表示）
3. 初始化（dp 表中特别的初始值，保证填 dp 表时不会越界，来源：题目要求+状态表示）
4. 填表顺序（根据状态转移方程修改 dp[ i ] 的方式，来源：题目要求+状态表示）
5. 返回值（题目求解的结果，来源：题目要求+状态表示）

二、相关例题

1）第 N 个泰波那契数

1137. 第 N 个泰波那契数

.1- 题目解析

        由题，题目的公式其实可以变形，从而得到如下公式：

        由题，dp[i] 的含义可以是第 i 个泰波那契数的值，由此可得状态转移方程即为泰波那契数的公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

        特别的，第 0 个泰波那契数为 0，第 1 个和第 2 个泰波那契数为 1，也就是说 dp 表要做相应的初始化，即 dp[0] = 0、dp[1] = 1、dp[2] = 1。

        在根据状态转移方程填 dp 表时，需要用到已经计算过的状态，那么填表顺序就是从左往右依次填表。

        返回值则为第 N 个泰波那契数，即 dp[n]。

【补】滚动数组思想进行空间优化

        假设有 a、b、c、d 四个变量，分别对应了泰波那契数列的前四个数，要求得第 n 个泰波那契数，只需让这四个变量按照如下方式，不断进行赋值操作即可：

• d = a + b + c;
• a = b;
• b = c;
• c = d;

        在 a、b、c、d 不断向数列后面移动的过程中，这四个变量组成的一个序列就在数列中整体向后遍历。

.2- 代码编写

class Solution {
public:
    int tribonacci(int n) {
        if(n==0)return 0;//处理边界情况
        if(n==1 || n==2)return 1;
        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];
    }
};

class Solution {
public:
    int tribonacci(int n) {
            if(n <= 1) // 处理边界
                return n;
 
            int a = 0, b = 1, c = 1, d = 1; // 滚动数组思想优化空间
            for(int i = 3; i <= n; ++i)
            {
                d = a + b + c;
                a = b;
                b = c;
                c = d;
            }
            return d;
    }
};

2）三步问题

面试题 08.01. 三步问题

.1- 题目解析

        以示例 1 为例，从楼梯下（即第 0 阶）上到第 1 阶，跨出一步即可，也就只有一种方式；

到第 2 阶可以一步一步地跨，也可以一次性跨两步，就有两种方式；到第 3 阶，可以一步一步跨，也可以一次性跨三步，还可以先跨一步再跨两边，或先跨两步再跨一步，一共有四种方式；到第 4 阶可以一步一步跨，或两步两步地跨，也可以先跨一步再跨三步，或先跨三步再跨一步，还可以先跨一步再跨一步再跨两步，或先跨一步再跨两步再跨一步，或先跨两步再跨一步再跨一步，一共有七种方式......以此类推，不难发现，从第 3 阶开始，相邻三阶各自的方式之和是下一阶的方式。

       由此，dp[i] 的含义可以是上到第 i 阶的方式，而状态转移方程即为：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

        特别的，上到第 1 阶的方式为 1，第 2 阶的方式为 2，第 3 阶的方式为 4，也就是说 dp 表要做相应的初始化，即 dp[0] = 0、dp[1] = 1、dp[2] = 2、dp[3] = 4。

        在根据状态转移方程填 dp 表时，需要用到已经计算过的状态，那么填表顺序就是从左往右依次填表。

        返回值则为上到第 N 阶的方式，即 dp[n]。

.2- 代码编写

class Solution {
public:
    int waysToStep(int n) {
        if(n==1 ||n==2)return n;
        if(n==3)return 4;

        const int MOD=1e9+7;//按题目要求特殊处理结果
        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）使用最小花费爬楼梯

746. 使用最小花费爬楼梯

.1- 题目解析

        如果 dp[ i ] 表示到达 i 位置的最小花费，则到达dp[ i ] 就有以下两种情况：

• 先到达dp[ i-1 ] ，然后支付cost[ i-1] 到达 dp[ i ]。
• 先到达dp[ i-2 ] ，然后支付cost[ i-2] 到达 dp[ i ]。

        题意及取两种情况小的那个，则得到状态转移方程：dp[i] =min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。此外，填表顺序为从左往右，要将第 0 阶和第 1 阶的花费初始化为 0，即dp[0]=0，dp[1]=0，返回值则为 dp[n]。

---

        而如果 dp[ i ] 表示从 i 位置出发，到达楼顶，此时的最小花费，则dp[ i ] 就有以下两种情况：

• 支付 cost[ i ]，往后走一步，从 i + 1的位置出发到终点。
• 支付 cost[ i ]，往后走两步，从 i + 2的位置出发到终点。

        则需要知道 i + 1 和 i + 2 位置的最小花费，及dp [i + 1] 和 dp[i + 2]，那么就需要从右往左填，且状态转移方程为：dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])。特别的，由于需要用到后两个已求得的状态来求当前状态，因此 dp 表的结尾两个位置就需要初始化，即 dp[n-1] = cost[n-1]，dp[n-2] = cost[n-2]；且返回值为 dp[0] 和 dp[1] 中的较小者。

.2- 代码编写

//dp[ i ] 表示到达 i 位置的最小花费
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1);
        dp[0]=dp[1]=0;
        for(int i=2;i<=n;i++)   
            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);

        return dp[n];
    }
};

//dp[ i ] 表示从 i 位置出发，到达楼顶，此时的最小花费
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1);
        dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
        for(int i=n-3;i>=0;i--)
            dp[i]=cost[i]+min(dp[i+1],dp[i+2]);
        return min(dp[0],dp[1]);
    }
}; 

4）解码方法

91. 解码方法

.1- 题目解析

        dp[i] 可以表示，以 i 位置为结尾时，解码方法的总数。

        关于 i 位置的编码状况，可以分为下面两种情况：

• 让 i 位置上的数单独解码成一个字母
• 让 i 位置上的数与 i - 1 位置上的数结合，解码成一个字母

        如此，让 i 位置上的数单独解码成一个字母，就存在 解码成功 和 解码失败 两种情况：

• 解码成功：dp[i] = dp[i - 1]，在 [0，i] 上所有解码结果后面填上一个字母即可。
• 解码失败：dp[i] = 0，前面努力都白费。

        而让 i 位置上的数与 i - 1 位置上的数结合在⼀起，解码成一个字母，同样也存在解码成功和解码失败两种情况：

• 解码成功：dp[i] = dp[i - 2]，在 [0，i] 上所有解码结果后面填上一个字母即可。
• 解码失败：dp[i] = 0，前面努力都白费。

        综上，以 i 位置为结尾时解码方法的总数即为 dp[i] = dp[i - 1] + dp[i - 2]，填表顺序为从左往右。

【补】处理边界情况和初始化问题的技巧

.2- 代码编写

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n);
        dp[0]=s[0]!='0';
        if(n==1)return dp[0];

        if(s[0]!='0' && s[1]!='0')dp[1]+=1;
        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]!='0')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];
    }
};

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