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

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

---

---

前言

dp_斐波那契数列模型_四道题

1. 第 N 个泰波那契数
2. 三步问题
3. 最小花费爬楼梯
4. 解码方法

---

一、第 N 个泰波那契数

1、题目

2、算法原理

1. 状态表示
   
   确定dp[i]表示：第i个泰波那契数的值

2. 状态转移方程

   由题目可知：$T_{n+3}=T_n+T_{n+1}+T_{n+2}$
   可得$T_n=T_{n-3}+T_{n-2}+T_{n-1}$
   =>状态转移方程dp[i] = dp[i-3] +dp[i-2] +dp[i-1]

3. 初始化
   
   保证填表时不越界//例如dp[0] = dp[-3] +dp[-2] +dp[-1] => 数组越界××× =>数组越界

   dp[i] = dp[i-3] +dp[i-2] +dp[i-1]

   dp[0] =0，dp[1] =dp[2] =1

4. 填表顺序

   由上图可知，为了填写当前位置的dp表，需要之前的表中的数值
   因此填表顺序为从左向右

5. 返回值

   根据题目要求，返回dp[n]

3、代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

二、三步问题

1、题目

2、算法原理

1. 状态表示

   

   确定dp[i]表示：到达i位置是，一共有多少种方法

2. 状态转移方程
   

以i位置的状态，最近的一步，来划分问题

• 从i-1到i，有dp[i-1]种方法
• 从i-2到i，有dp[i-2]种方法
• 从i-3到i，有dp[i-3]种方法

那么从 “前一步” 位置到i位置一共有dp[i] 种方法：

=> dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

3、初始化

保证填表时不越界

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

4、填表顺序
从左往右

5、返回值

根据题目要求，返回dp[n]

3、代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

三、最小花费爬楼梯

1、题目

2、算法原理

1. 状态表示

   确定dp[i]表示：到达i位置的最小花费

2. 状态转移方程
   一次可以走一个或两个台阶
   

用之前的状态推导出dp[i]的值

根据最近的一部来划分问题：

• 先到i-1位置，然后支付cost[i-1]，走一步到达 i
  • dp[i-1]+cost[i-1]
• 先到i-2位置，然后支付cost[i-2]，走两步到达 i
  • dp[i-2]+cost[i-2]

=> dp[i] = min｛dp[i-1]+cost[i-1]，dp[i-2]+cost[i-2]｝

3、初始化

保证填表时不越界

dp[0] =dp[1] =0

4、填表顺序
从左往右

5、返回值

根据题目要求，返回dp[n]

3、代码

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-1]+cost[i-1],dp[i-2]+cost[i-2]);
        return dp[n];        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

---

四、解码方法

1、题目

2、算法原理

1. 状态表示

   确定dp[i]表示：以i位置结尾时，解码方法的总数

2. 状态转移方程
   

例如s[i]单独解码如果成功那么，总的解码方法就是前i-1个位置总的解码方法，因为当前i-1个解码共有dp[i-1]种方法，再解码s[1]成功，只需要在这dp[i-1]种方法之后再加一个字母就可以，因此当s[i]解码成功时dp[i]=dp[i-1];

3、初始化

4、填表顺序
从左往右

5、返回值

根据题目要求，返回字符串最后一个字母位置的解码总数，返回dp[n-1]

3、代码

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(10<= t && 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(10<= t && t<=26) 
            dp[i]+=dp[i-2];
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

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