动态规划刷题

文章目录 动态规划三步问题题目解析代码

动态规划

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]; } };