60题学会动态规划系列：动态规划算法第一讲

坚持就是胜利 - - 

1.第N个泰波那切数

力扣链接：力扣

泰波那契序列 Tn 定义如下： 

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

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

 首先我们分析一下题目，在n>=0的条件下也就是说都是正数，然后给了一个算泰博纳妾数的公式，这道题很简单，但是我们还是一步步带着大家来分析：

首先在我们以后做动态规划的题，都按照一下这个模板来编写：

1.状态表示

首先我们先把公式重新推导一下，让每边减3得到Tn = Tn-3 + Tn-2 + Tn-1 ，Tn就是第n个泰博纳妾数，根据前三个泰波纳妾数推导出来的第n个，所以说dp[i]的状态就是第i个泰波纳妾数

2.状态转移方程

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]    因为第i个泰波纳妾数等于前三个泰波纳妾数的和，所以转移方程就是这个

3.初始化

我们初始化的目的是为了防止越界，如下图：

第0个泰波那切数的前三个都是非法的，所以我们必须给定第0个泰波纳妾数，同理dp[1]和dp[2]同样会越界，而题目又贴心的给了我们初始值，dp[0] = 0,dp[1] = 1,dp[2] = 1 

4.填表以及确定填表顺序

因为我们是知道左边的值，依靠左边的值推出来右边的值，所以顺序是从左向右

5.返回值

既然让我们返回第n个泰波纳妾数，而我们的状态表示dp[i]就表示第i个泰波纳妾数，所以返回dp[n]就是第n个泰波纳妾数

思路理解了我们直接写代码：

class Solution {
public:
    int tribonacci(int n) {
        //1.创建dp表
        //因为是从0开始的所以要多开一个位置
        vector<int> dp(n+1);
        //处理边界条件
        if (n==0) return 0;
        if (n==1||n==2) return 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];
        }
        //返回值
        return dp[n];
    }
};

 首先创建dp表，由于是从0开始的所以要多开一个位置存储第n个泰波纳妾数，所以空间大小为n+1，因为第0个，第1个，第2个泰波那切数都给出来了，所以我们只需要从第3个泰波那切数开始计算，然后我们处理边界条件，如果不处理那么数组会直接越界，最后返回dp[n]即可。 

下面我们再讲解一下用滚动数组优化的方式，在上面的代码中我们要求第n个太波那契数列数是没必要将n之前的所有泰波那契数都保存的，我们只需要保存前三个就可以算出来了，所以我们只需要用四个变量就能解决这个问题：

 一开始d是第3个泰波那契数，经过滚动后下一次d变成了第4个泰波那契数，下面我们实现一下代码：

class Solution {
public:
    int tribonacci(int n) {
        //初始化前3个泰波那契数
        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;
        if (n==0) return 0;
        if (n==1||n==2) return 1;
        for (int i = 3;i<=n;i++)
        {
            d= a+b+c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

 需要注意的是：滚动的时候应该是a向d去依次赋值，不能反过来反过来会导致原本c的值被覆盖。

2.三步问题

力扣链接：力扣

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

 首先题目说有n阶台阶，小孩一次可以上1阶或者2阶或者3阶，然后求有多少种上楼的方式，然后还说了题目结果会很大需要取模，下面我们就演示一下上楼梯的步骤：

 首先从地平线到第一个台阶只有一种方法，所以第一个台阶的方法数就是1.

到达第二个台阶可以从第0个台阶跨越2步到达（这是一种方法），也可以从第一个台阶跨越1步到达，由于要想从第一个台阶到第二个台阶就得先到第一个台阶，而到达第一个台阶的方法数是1，所以从第一个台阶到达第二个台阶的方法数为1*1==1.所以到达第二个台阶的总次数为2

到达第三个台阶可以直接从第0个台阶跨越3步到达，也可以从第一个台阶跨越2步到，还可以从第二个台阶跨越1步到达。首先从第0个台阶跨越3步到达方法数是1，从第一个台阶跨越需要知道到达第一个台阶的方法数所以是1*1==1，从第二个台阶跨越1步到达首先要计算到达第二个台阶的方法数所以是2*1 == 2，所以总次数为1 + 1 + 2 = 4.

到达第4个台阶可以从第一个台阶直接跨越3步，也可以从第二个台阶跨越2步，也可以从第3个台阶跨越一步。第一个台阶直接跨越3步的方法数为：1*1==1，第二个台阶跨越2步的方法数为2*1==2，第3个台阶跨越一步的方法数为4*1==4，所以总方法数为1+2+4==7

下面我们直接套模板：

1.状态表示

我们可以看到如果是第5个台阶的话那么有13种方法，而我们创建一个dp表将每个台阶的方法数放入，如下图：

所以dp[i]就表示第i个台阶的方法数。 

2.状态转移方程

可以通过图看到，第5个台阶的方法数是前3个台阶的方法数之和，所以状态转移方程为：

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

3.初始化

由于第0,1,2个台阶会越界，所以我们直接给出方法数：dp[0] = 1,dp[1] = 1,dp[2] = 2,这里可能有人会有疑问，为什么到达地平线还有1个方法呢？在这里我们只能说要算第3个台阶的方法数dp[0]必须给1，这是靠分析题目得出来的。

4.填表

从左向右填表

5.返回值

dp[i]表示第i个台阶的方法数，所以返回dp[n]即可。

class Solution {
public:
    int waysToStep(int n) {
       const int MOD = 1e9+7;
       //创建dp表
       vector<int> dp(n+1);
       //解决边界问题
       if (n==0||n==1) return 1;
       if (n==2) return 2;
       dp[0] = 1,dp[1] = 1,dp[2] = 2;
       for (int i = 3;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，我们大多数人都会认为楼顶就是数组的最后一个位置也就是20的位置，如果是20那么答案应该是10才对，为什么是15呢？因为楼顶其实是在数组最后一个位置的下一个位置：

了解了这个后我们讲一下如何计算：

首先能到达顶楼的位置有两个，要不然是顶楼-1的位置，要不然就是顶楼-2的位置，因为题目已经告诉了每次只能爬一个台阶或者两个台阶。所以我们只需要求出顶楼-1位置的最小花费和顶楼-2位置的最小花费的较小值，我们以实例1为例：

 由于题目已经告诉从0或1开始爬楼梯，所以到达0位置和1位置的最小花费是0.15是第一个台阶到达第一个台阶最小花费是0，然后15跨两步到楼顶需要支付15，所以15->楼顶的最小花费是15.

要计算20这个台阶的最小花费就要先知道哪两个台阶能到20这个位置，很明显从第0个台阶跨两步到20，到达第0个台阶的花费为0，从第0个台阶到第2个台阶的花费为10，所以10->20的花费为10，同理15->20的花费为15，那么到台阶2的最小花费就是10，然后从20->楼顶的花费是20,所以20->楼顶的最小花费是10+20==30。

取楼顶-1台阶的最小值和楼顶-2台阶的最小值相比较，最小的就是到楼顶的最小值，所以刚刚的实例2答案为15.

1.状态表示

dp[i]表示到达第i个台阶的最小花费

2.状态转移方程

dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.初始化

因为题目告诉了从第0个台阶或者第1个台阶开始爬，所以之前到达0或1台阶的最小花费是0，所以dp[0]和dp[1]都等于0

4.填表

5.返回值

由于数组是从0开始的，size()的大小就是楼顶的位置，所以返回dp[size()]即可。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if (cost.size()<=0)
        {
            return 0;
        }
        //创建dp表
        int sz = cost.size();
        vector<int> dp(sz+1);
        //初始化
        dp[0] = dp[1] = 0;
        for (int i = 2;i<=sz;i++)
        {
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[sz];
    }
};

 上面我们是按照从前往后推的下面我们也可以换一个思想，从后往前推：

 比如我们现在在第7个台阶，那么我们支付了第7个台阶的费用后可以向后走一步也可以走两步，走一步到第8个台阶，第8个台阶花费100直接能到楼顶。走两步到第9个台阶，花费1直接就能到楼顶，这个时候我们第7个台阶到达楼顶的最小花费就是：第8个台阶和第9个台阶到达楼顶的最小花费的最小值，所以第7个台阶的最小花费就是1+1（+1是因为自己支付了费用要向后跳），以此类推从第7个台阶推到第0个台阶，又因为我们是从0或1出发，所以最后的返回值是0位置和1位置最小花费的最小值。

1.状态表示

dp[i]表示从i位置支付费用后到达楼顶花费的最小值

2.状态转移方程

dp[i] = min(dp[i+1],dp[i+2]) + cost[i]   (要记住我们从i位置起跳是需要花钱的所以要加上cost[i]）

3.初始化

可以看到我们的转移方程是i+1和i+2，所以在距离楼顶的2个位置和1个位置的台阶是无法计算的因为越界了，并且从这两个位置起跳到楼顶只需要花费自身cost的费用。所以dp[楼顶-1] = cost[楼顶-1],dp[楼顶-2] = cost[楼顶-2]

4.填表

从右向左填表：

5.返回值

返回dp[0]和dp[1]的较小值

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //创建dp表
        int sz = cost.size();
        vector<int> dp(sz);
        //初始化
        dp[sz-1] = cost[sz-1];
        dp[sz-2] = cost[sz-2];
        for (int i = sz-3;i>=0;i--)
        {
            dp[i] = min(dp[i+1],dp[i+2]) + cost[i];
        }
        return min(dp[0],dp[1]);
    }
};

4.解码方法

力扣链接：力扣

 首先我们要能读懂题，我们做的是解码工作，题目会给我们一个数字字符串，然后我们可以有多少种方法将数字转化为不同的字符顺序，要注意的是一旦有0作为前导就会解码失败，可以看实例3。（但是如果是两个字符，比如10那么可以解码为K那么就是一种方法）.首先题目要求字符串的解码总数，那我们根据经验就可以得出状态表示，解码总数就是以字符串最后一个字符为结尾的总解码数。

1.状态表示

dp[i]表示以i字符为结尾的总解码数

2.状态转移方程

首先我们要知道dp[i]的方法数就要看s[i]这个字符能否解码，如果这个字符>='1'并且<='9'那么就是可以解码的，一旦这个字符可以解码就说明总方法数是dp[i-1]，如下图：

 比如上图中dp[i]有三种方法分别是abc,acb,cba，当s[i]可以解码时就可以放在他们的后面，但是方法还是3种，因为我们要求的是以i为结尾的方法数而不是字符个数！当s[i]为0时那么在前面的所有努力都白费了，直接dp[i]等于0

当我们的s[i]可以和s[i-1]相结合变成一个新的字符时，那么就可以把s[i]和s[i-1]看成一个字符，那么总方法数就是前面i-2的方法数，所以是dp[i-2]

3.初始化

状态转移方程中只有0和1位置会越界，所以初始化0和1

首先如果第一个字符是>='1'&&<='9'，那么dp[0]就是1，否则就是0

如果第2个字符可以解码，那么方法数就是i-1的方法数那就是1，如果第二个字符还可以和第一个字符结合，那么方法数就变成2

4.填表

已知0和1位置，所以从左向右填表：

5.返回值

返回以字符串最后一个字符为结尾的总方法数

class Solution {
public:
    int numDecodings(string s) {
      //创建dp表
      int sz = s.size();
      vector<int> dp(sz,0);
      //初始化
      dp[0] = s[0]!='0';
      //解决边界条件
      if (dp[0]==0) return 0;
      if (sz==1) return dp[0];
      //初始化
      if (s[1]>='1'&&s[1]<='9')
      {
          dp[1] = 1;
      }
      int t = (s[0]-'0')*10 + s[1]-'0';
      if (t>=10&&t<=26)
      {
          ++dp[1];
      }
      for (int i = 2;i<sz;i++)
      {
          if (s[i]>='1'&&s[i]<='9')
          {
              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[sz-1];
    }
};

 需要注意的是如果s[0]为0那么是不能解码的，当字符串长度为1时要返回dp[0]也就是第一个字符的方法数，否则我们下面的初始化dp[1]会越界。

下面我们讲一下能优化初始化的思路：

我们可以给dp表多开一个空间，这个位置放的值要视情况而定，如下图：

 我们在原先dp表的基础上多开了一个位置，那么这个位置该放多少呢？首先我们知道，第一个字符是一定要初始化的，第一个字符对应的dp表的位置再dp[1]，我们将这个位置初始化使用动态转移方程的时候才不会越界（只要满足i-1,i-2不越界），dp[1]是我们自己初始化的，dp[2]需要状态转移方程计算，当第二个字符可以解码那么方法数是dp[i-1]也就是第一个字符的方法数1，然后第二个字符还可以和第一个字符结合，一旦结合解码数就变成dp[i-2]，而dp[i-2]是我们的虚拟位置，如果我们第一个虚拟位置初始化为0，计算dp[i-2]的时候就会少一个方法数，所以1才是正确的，我们也可以再举一个例子：

 拿"2 0"来说，0位置的方法数是dp[i-1]+dp[i-2]，由于是0所以dp[i-1]是0，dp[i-2]是我们的虚拟位置，2和0是可以结合的所以要有一种方法，如果虚拟位置为0就是0种方法就错了，所以虚拟位置应该为1.有了虚拟位置那么计算对应的字符串都需要-1，原来-1的要变成-2的字符，比如dp[i]的方法数是s[i-1]位置的字符的方法数。

class Solution {
public:
    int numDecodings(string s) {
      //创建dp表
      int sz = s.size();
      vector<int> dp(sz+1,0);
      //初始化
      dp[0] = 1;
      dp[1] = s[0]!='0';
      for (int i = 2;i<=sz;i++)
      {
          if (s[i-1]>='1'&&s[i-1]<='9')
          {
              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[sz];
    }
};

可以看到此方法不仅简化了代码而且让我们的初始化变的更简单。文章来源地址https://www.toymoban.com/news/detail-464090.html

到了这里，关于60题学会动态规划系列：动态规划算法第一讲的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！