【动态规划专栏】--基础-- 动态规划经典题型_c++动态规划经典题目详解

​

#： 初始化：

#： 返回值：

class Solution {
public:
    int tribonacci(int n) {
 
        // 处理边界情况
        if(n == 0) return 0;
        if(n <= 2) return 1;
 
        // 1、创建dp表
        vector<int> dp(n + 1,0);
 
        // 2、初始化
        dp[1] = 1, dp[2] = 1;
 
        // 3、填表
        for(int i = 3; i<=n; i++)
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
 
        // 4、返回值    
        return dp[n];
    }
};

​

class Solution {
public:
    int tribonacci(int n) {
 
        // 处理边界情况
        if(n == 0) return 0;
        if(n <= 2) return 1;
        
        // 1、创建 dp 表
        vector<int> val(3,0);
 
        // 2、初始化
        val[1] = 1, val[2] = 1;
        int tmp = 0;
 
        // 3、填表
        for(int i = 3; i<=n; i++)
        {
            tmp = val[0] + val[1] + val[2];
            val[0] = val[1], val[1] = val[2], val[2] = tmp;
        }
            
        // 4、返回
        return tmp;
    }
};

1. 上⼀步上⼀级台阶， dp[i] += dp[i - 1] ；
2. 上⼀步上两级台阶， dp[i] += dp[i - 2] ；
3. 上⼀步上三级台阶， dp[i] += dp[i - 3] ；

#： 初始化：

#： 返回值：

class Solution {
public:
    int waysToStep(int n) {
 
        // 处理边界情况
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
 
        // 1、创建 dp 表
        vector<int> dp(n + 1, 0);
 
        // 2、初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
 
        // 3、填表
        for(int i = 4; i <= n; i++)
            dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
 
        // 4、返回
        return dp[n];
    }
};

class Solution {
public:
    int waysToStep(int n) {
 
        // 1、创建 dp 表
        vector<int> dp(4, 0);
 
        // 2、初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
 
        // 处理边界情况
        if(n <= 3) return dp[n];
 
        // 3、填表
        uint64_t tmp = 0;
        for(int i = 4; i <= n; i++)
        {
            tmp = ((dp[1] + dp[2]) % 1000000007 + dp[3]) % 1000000007;
            dp[1] = dp[2], dp[2] = dp[3], dp[3] = tmp;
        }
 
        // 4、返回
        return tmp;
    }
};

1. 先到达 i - 1 的位置，然后支付 cost[i - 1] ，接下来走⼀步走到 i 位置：dp[i - 1] + csot[i - 1] 
2. 先到达 i - 2 的位置，然后支付 cost[i - 2] ，接下来走⼀步走到 i 位置：dp[i - 2] + csot[i - 2] 

#： 初始化：

#： 返回值：

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

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        
        // 处理边界情况
        if(cost.size() == 2) return min(cost[0], cost[1]);
 
        // 1、创建dp表
        vector<int> dp(2, 0);
 
        // 2、初始化
        dp[0] = 0, dp[1] = 0;
 
        // 3、填表
        int tmp = 0;
        for(int i = 2; i <= cost.size(); i++)
        {
            tmp = min(cost[i - 1] + dp[1], cost[i - 2] + dp[0]);
            dp[0] = dp[1], dp[1] = tmp;
        }
 
        // 4、返回
        return tmp;
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        
        // 处理边界情况
        if(cost.size() == 2) return min(cost[0], cost[1]);
 
        int n = cost.size();
        // 1、创建dp表
        vector<int> dp(n, 0);
 
        // 2、初始化
        dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
 
        // 3、填表
        for(int i = n - 3; i >= 0; i--)
            dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];
 
        // 4、返回
        return min(dp[0], dp[1]);
    }
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 处理边界情况
        if(cost.size() == 2) return min(cost[0], cost[1]);
 
        // 1、创建dp表
        vector<int> dp(2, 0);
 
        // 2、初始化
        dp[1] = cost[cost.size() - 1], dp[0] = cost[cost.size() - 2];
 
        // 3、填表
        int tmp = 0;
        for(int i = cost.size() - 3; i >= 0; i--)
        {
            tmp = min(dp[0], dp[1]) + cost[i];
            dp[1] = dp[0], dp[0] = tmp;
        }
 
        // 4、返回
        return min(dp[0], dp[1]);
    }
};