【动态规划入门修炼手册】——泰波那契数（滚动数组空间优化）|三步问题

一、动态规划思路求解问题

• 1.状态表示
  动态规划的状态表示，通俗点讲就是确定dp数组的含义。
  
• 2.状态转移方程
  状态转移方程通俗来讲就是：确定dp数组的递推公式
  
• 3.确定如何初始化
  
• 4.确定遍历顺序
  
• 5.返回值
  

二、泰波那契数

题目

求解思路

• 1.确定dp[i]的含义
  对于这道题来说，题目明确地表示Tn就相当于这里地dp[i]，所以dp数组的含义较为清晰地给出。

dp[i]表示：第i个泰波那契数的值是dp[i]

• 2.确定递推公式：

题目已经给出：

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

• 3.确定如何初始化

由题目可知，初始化顺序为：dp[0] = 0,dp[1] = 1,dp[2] = 1

• 4.确定遍历顺序

从i = 3开始，每一个泰波那契数都是由它的前三个泰波那契数相加得来的

所以我们应该从前往后遍历。

• 5.返回值

返回值为dp[n]

具体代码如下：

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

时间复杂度O(n)，空间复杂度O(n)

空间优化：滚动数组

在这道题中，我们知道每一个泰波那契数都是由前三个泰波那契数推导所得，所以我们只要知道前三个泰波那契数，就可以推导出后面的数，所以我们可以先用三个变量分别保存前三个泰波那契数然后求出第四个泰波那契数并保存在变量中，然后将这四个数变量往后移动，就形成了滚动数组。

具体代码如下：

class Solution {
public:
    int tribonacci(int n) 
    {
        //空间优化：滚动数组
        //    i：  0  1  2  3  4  5
        //dp[i]:   0  1  1  2  4  7
        //向后滚动
        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;
    }
};

时间复杂度O(n)，空间复杂度O(1)

三、三步问题

链接在此

求解思路

• 1.确定dp[i]的含义

根据题意我们可以知道，小孩走第一个台阶有1种方法，走第二个台阶有2种方法

所以我们可以确定

dp[i]表示：走第i个台阶有dp[i]种方法

• 2.确定递推公式：

由题意，dp[1] = 1,dp[2] = 2,dp[3] = 4;

也就是走第三个台阶有4种方法，分别是：

• 1.每次都走1步
  2.第一次走1步，第二次走2步
  3.第一次走2步，第二次走1步
  4.一次走3步

那么走第4层台阶有多少种方法呢？

我们知道，第4种方法一定是由下面3种情况所得：

• 1.由第一层台阶走3步到达第4层
• 2.由第二层台阶走2步到达第4层
• 3.由第三层台阶走1步到达第4层

前面已经知道，走第一层台阶有1种方法，走第二层台阶有2种方法，走第三层台阶有4种方法。

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

如果你理解成这样：

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

你就没有搞清楚dp[i]的含义是什么，dp[i]表示走第i个台阶有dp[i]种方法

如果你这样理解，含义就是走到第4层台阶要走多少步。

所以走到第i层台阶的方法数是由第i-1 + i-2 + i-3 层台阶的方法数相加所得结果。

递推公式为：

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

• 3.确定如何初始化

由题目可知，初始化顺序为：dp[1] = 1,dp[2] = 2,dp[3] = 4

• 4.确定遍历顺序

从i = 4开始，走到每一层台阶的方法数都是由前3层台阶的方法数相加。

所以我们应该从前往后遍历。

• 5.返回值

返回值为dp[n]

注意：dp[0]表示走到第0层台阶的方法数是dp[0]，并没有任何意义

class Solution 
{
public:
    int waysToStep(int n) 
    {
        if(n == 3)
            return 4;
        else if(n < 3)
            return n ;
        vector<long long> 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] + dp[i-3]) % 1000000007;
        }
        return dp[n] % 1000000007;
    }
};

总结

今天开始学习动态规划的相关内容，后续会不断更新，长期的过程，坚持就对了！