> 技术文档 > 动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n 1 + a

动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n 1 + a


1.第 N 个泰波那契数

题目链接
泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入: n = 4
输出: 4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2:

输入: n = 25
输出: 1389537

dp[i]就是第i个泰波那契数

我们这个题直接返回dp[n]就行了

为了保证不出现越界的情况,我们将前3个位置进行初始化,这里题目中已经说了具体初始化为什么
填表的顺序是从左向右进行就行了

class Solution{public:    int tribonacci(int n)    {         //处理边界问题(n太小的话是会出现越界的情况的)        if(n==0)return 0;        if(n==1||n==2)return 1;        //1.创建一个dp表        vectordp(n+1);         //2.初始化        dp[0]=0,dp[1]=dp[2]=1;         //3.填表        for(int i=3;i<=n;i++)        {            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];        }         //4.返回值        return dp[n];    }};

可以利用滚动数组进行空间优化
就是创建四个变量然后一直不停的移动
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a

class Solution{public:    int tribonacci(int n)    {         //处理边界问题(n太小的话是会出现越界的情况的)        if(n==0)return 0;        if(n==1||n==2)return 1;        int a=0,b=1,c=1,d=0;        //3.填表        for(int i=3;i<=n;i++)        {            d=a+b+c;            //三个指针往右边进行移动操作            a=b;            b=c;            c=d;        }        //4.返回值        return d;    }};

2.三步问题

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

示例 1:

输入:n = 3
输出:4
说明: 有四种走法

示例 2:

输入:n = 5
输出:13

提示:

  1. n 范围在[1, 1000000]之间

这里我们的dp[i]分成三种情况
从[i-1]位置走一步到[i]位置 dp[i-1]种方法
从[i-2]位置走两步到[i]位置 dp[i-2]种方法
从[i-3]位置走三步到[i]位置 dp[i-3]种方法

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

初始化:保证不越界
先将前三个进行初始化操作

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

class Solution{public:    int waysToStep(int n)    {         const int MOD=1e9+7;         //创建一个dp表        vectordp(n+1);         //边界条件处理        if(n==1||n==2)return n;        if(n==3)return 4;        //填表之前进行一个初始化操作        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.使用最小花费爬楼梯

使用最小花费爬楼梯
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入: cost = [10,15,20]
输出: 15
解释: 你将从下标为 1 的台阶开始。

  • 支付 15 ,向上爬两个台阶,到达楼梯顶部。
    总花费为 15 。

示例 2:

输入: cost = [1,100,1,1,1,100,1,1,100,1]
输出: 6
解释: 你将从下标为 0 的台阶开始。

  • 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
  • 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
  • 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
  • 支付 1 ,向上爬一个台阶,到达楼梯顶部。
    总花费为 6 。

dp[i]标示的是到达i位置的最小花费动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a

初始化
保证填表的时候不越界
我们是需要将dp表前两个位置进行初始化操作
dp[0]和dp[1]都初始化为0

结果返回dp[n]就行了

class Solution{public:    int minCostClimbingStairs(vector& cost)    {        //创建一个dp表        //2.初始化        //3.填表        //4.返回结果         int n=cost.size();        vectordp(n+1);        //dp[0]=dp[1]=0;  我们这里就不需要写了,因为我们在创建dp表的时候已经进行了初始化操作了         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];    }};

解法二:从i位置为起点
dp[i]标示:从i位置出发,到达楼顶,此时的最小花费
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a

class Solution{public:    int minCostClimbingStairs(vector& cost)    {        //创建一个dp表        //2.初始化        //3.填表        //4.返回结果         int n=cost.size();        vectordp(n);         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.解码方法

解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

\"1\" -> \'A\' \"2\" -> \'B\' ... \"25\" -> \'Y\' \"26\" -> \'Z\'

然而,在 解码 已编码的消息时,你意识到有许多不同的方式来解码,因为有些编码被包含在其它编码当中(\"2\" 和 \"5\" 与 \"25\")。

例如,\"11106\" 可以映射为:

  • \"AAJF\" ,将消息分组为 (1, 1, 10, 6)
  • \"KJF\" ,将消息分组为 (11, 10, 6)
  • 消息不能分组为  (1, 11, 06) ,因为 \"06\" 不是一个合法编码(只有 “6” 是合法的)。

注意,可能存在无法解码的字符串。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串,返回 0

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入: s = “12”
输出: 2
**解释:**它可以解码为 “AB”(1 2)或者 “L”(12)。

示例 2:

输入: s = “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3:

输入: s = “06”
输出: 0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

dp[i]表示:以i位置为结尾时,解码方法的总数
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a
所以我们的状态方程就是dp[i]=dp[i-1]+dp[i-2]
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a
返回值是dp[n-1]

class Solution{public:    int numDecodings(string s)    {        //创建dp表        //初始化        //填表        //返回值         int  n=s.size();        vectordp(n+1);         //初始化一开始的两个位置的dp表        dp[0]=s[0]!=\'0\';//说明能单独编码        //处理下边界条件        if(n==1)return dp[0];//如果只有一个字符的话我们直接返回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=10&&t<=26)dp[i]+=dp[i-2];        }        return dp[n-1];     }};

这里初始化的长度太长了,我们可以进行优化下
其实就是处理边界问题和初始化问题的技巧

注意事项:
1.虚拟节点里面的值,要保证后面的填表是正确的

2.下标的映射关系
就是将我们的dp表往右边挪动了一位
动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n   1 + a

class Solution{public:    int numDecodings(string s)    {        //创建dp表        //初始化        //填表        //返回值         int  n=s.size();        vectordp(n+1);         //初始化一开始的两个位置的dp表        dp[0]=1;//虚拟节点初始化为1,保证后面的填表是正确的        dp[1]=s[1-1]!=\'0\';        //上面已经将前两个位置初始化好了,现在我们从第三个位置进行初始化操作就行了        for(int i=2;i=10&&t<=26)dp[i]+=dp[i-2];        }        return dp[n];     }};

这里所有要设计到找之前的字符的,我们都要多减一个1