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

时间:2024-10-15 07:19:44

【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];
    }
};