当前位置：首页 > article >正文

动态规划刷题

article 2025/3/4 16:42:57

文章目录

动态规划
- 三步问题
- 题目解析
- 代码

动态规划

1. 状态表示：dp[i]，表示dp表中i下标位置的值
2. 状态转移方程：以i位置位置的状态，最近的一步来划分问题，比如可以将状态拆分成前状态来表示现状态，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
3. 初始化
4. 填表顺序
5. 返回值
线性dp的状态表示dp[i]都是以某个位置为开头或者以某个位置为结尾

三步问题

在这里插入图片描述

题目解析

1. 状态表示：以i为结尾，dp[i]是什么意思，是一共有多少种方法
2. 状态转移方程：以i位置最近的一步来划分问题
3. 初始化：dp[1] = 1，dp[2] = 2，dp[3] = 4
4. 填表顺序：从左向右填表
5. 返回值：返回dp[n]的状态

在这里插入图片描述

代码

class Solution 
{
public:
    int waysToStep(int n) 
    {
        if(n == 1 || n == 2) return n;
        else if(n == 3) return 4;
        
        long long k = 1e9 + 7;

        vector<int> 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]) % k) + dp[i-3]) % k;
        } 

        return dp[n];
    }
};