【leetcode C++】动态规划

动态规划解题思路

1. 状态表示

dp表 里面的值所代表的含义（1.根据题目要求得出 2.经验 + 题目要求 3.分析问题过程中，发现重要子问题）

2. 状态转移方程

dp[i] 等于什么

3. 初始化

保证填表不越界

4. 填表顺序

为了填写该状态的时候，所需的状态已知

5. 返回值

题目要求 + 状态表示

6. 空间优化（平时做题可以不用考虑，面试复习）

一般用到滚动数组（仅仅需要若干状态）

1. 1137. 第 n 个泰波那契数

题目：

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

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

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

题目链接

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

文字分析

这里还可以进行空间优化：

这里用到 滚动数组，只需要三个数，就可以得到第 i 个数的值，开空间可以节省

代码

class Solution {
public:
    int tribonacci(int n) 
    {
        int a = 0,b = 1,c = 1;
        if(n == 0)
        {
            return 0;
        }
         if(n < 3)
        {
            return 1;
        }
         for(int i = 3;i <= n;i++)
         {
           int d = a + b + c;
           a = b;
           b = c;
           c = d;
         }
         return c;
    }
};

2. 08.01 三步问题

题目：

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

题目链接

11面试题 08.01. 三步问题 - 力扣（LeetCode）

文字分析

注意：

数据过大，储存会有误

在填表的时候，发生加法可以取模

代码

class Solution {
public:
    int waysToStep(int n) 
    {
       vector<int> s(n + 1);
       if(n == 1)
       {
        return 1;
       } if(n == 2)
       {
        return 2;
       } if(n == 3)
       {
        return 4;
       }
       s[0] = 0;
       s[1] = 1;
       s[2] = 2;
       s[3] = 4;
       for(int i = 4;i <= n;i++)
       {
         s[i] =( (s[i - 1] + s[i - 2]) %  1000000007 + s[i - 3] )% 1000000007;
       }
       return s[n];
    }
};

3. 746 使用最小花费爬楼梯

题目：

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

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

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

题目链接

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

文字分析

 代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = cost[0];
        dp[1] = cost[1];

        for(int i = 2;i < n;i++)
        {
            dp[i] = min(dp[i - 1] + cost[i],dp[i - 2] + cost[i]);
        }
        dp[n] =  min(dp[n - 1],dp[n - 2] );
        return dp[n];

    }
};