动态规划——斐波那契数列模型问题详解

动态规划——斐波那契数列模型问题详解

引用

CSDN

1.

https://m.blog.csdn.net/Dirty_artist/article/details/145462036

动态规划是算法领域的重要概念，广泛应用于各种问题的求解中。本文通过四个具体的LeetCode题目（泰波那契数、三步问题、最小花费爬楼梯、解码方法）来阐述动态规划的原理和实现方法。每个题目都包含了算法原理、代码实现的详细讲解，内容系统且深入。

1137. 第 N 个泰波那契数

算法原理

• 状态表示： 根据题目要求可得出
• 状态转移方程： 也是根据题目得出
  dp[i] 依赖前三个状态
  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
• 初始化： 保证填表不越界，根据题目可以得出

  dp[0] = 0;
  dp[1] = dp[2] = 1;
  

• 填表顺序： 根据前面的状态，计算当前状态
  从左向右
• 返回值： dp[i]

代码实现

class Solution {
public:
    int tribonacci(int n)
    {
        if(n == 0)  return 0;
        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];
    }
};

这里可以用空间优化，求当前状态的时候，只依赖前面3个状态。用滚动数组：

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

面试题 08.01. 三步问题

• 到1号位置：1种方法（起始位置上2个台阶）
• 到2号位置：
  起始位置直接上2阶
  1号位置上1阶（经过1号一种方法）
  1+1 = 2种方法
• 到3号位置
  从起始位置上3阶
  1号位置上2阶（经过1号一种方法）
  2号位置上1阶（经过2号两种方法）
  1 + 1 + 2 = 4种方法
• 到4号位置
  从1号位置上3阶（经过1号一种方法）
  从2号位置上2阶（经过2号两种方法）
  从3号位置上1阶（经过3号4种方法）
  1 + 2 + 4 = 7种方法
  之后就是同理……

算法原理

• 状态表示： 到达i号台阶一共有多少种方法
• 状态转移方程： 以i位置最近的一步（三种，因为可以跨1、2、3阶）
  即
  dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
• 初始化： 一个状态依赖前3个状态，刚刚上面推出了

  dp[1] = 1;
  dp[2] = 2;
  dp[3] = 4;
  

• 填表顺序： 从左往右
• 返回值： dp[i]

代码实现

class Solution {
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);
        int MOD = 1e9 + 7;
        //初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        //到达i台阶有多少种方法
        for(int i = 4; i <= n; i++)
        {
            //上台阶3种, 选取最近一步划分
            //i-1 i-2 i-3
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

题目有一个要注意的，到达楼梯顶，并不是数组末尾元素，而是在末尾元素的下一个位置

算法原理

• 状态表示： 以xx位置为结尾，xxx（题目要求）
  这里的xxx就是到达i位置的最小花费
• 状态转移方程： 以i位置最近的一步（两种，因为可以跨1、2阶）
  即
  dp[i] = min(dp[i-2]+cost[i-2], dp[i-1] + cost[i-1])
• 初始化(保证填表不越界)：

  dp[0] = dp[1] = 0;
  dp[2] = 2;
  dp[3] = 4;
  

• 填表顺序： 从左往右
• 返回值： dp[i]

代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        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. 解码方法

算法原理

• 状态表示： 以某个位置为结尾，xxx
  即
  dp[i]
  表示以i位置为结尾，解码方法的总数
• 状态转移方程： 根据最近一步，划分问题
• 初始化： 一个状态依赖前2个状态
• 填表顺序： 从左往右
• 返回值： dp[i-1]

代码实现

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 cmb = (s[0]-'0')*10 + (s[1]-'0');
        if(cmb >= 10 && cmb <= 26)
        {
            dp[1] += 1;
        }
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0')
            {
                dp[i] += dp[i-1];
            }
            cmb = (s[i-1]-'0')*10 + (s[i]-'0');
            if(cmb >= 10 && cmb <= 26)
            {
                dp[i] += dp[i-2];
            }
        }
        return dp[n-1];
    }
};

代码优化：
为什么虚拟节点可以填1？因为在原始的0和1位置拼接起来，要是能解码成功，说明找到了一种解码方式，是要加上dp[0]的值，如果dp[0]为0的话，就相当于忽略掉了。

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