动态规划刷题
动态规划1. 状态体现：dp，体现dp表中i下标位置的值
2. 状态转移方程：以i位置位置的状态，最近的一步来划分题目，比如可以将状态拆分成前状态来体现现状态，dp = dp + dp + dp
3. 初始化
4. 填表次序
5. 返回值
线性dp的状态体现dp都是以某个位置为开头或者以某个位置为结尾
三步题目
https://i-blog.csdnimg.cn/direct/253ab67d67f9430c827d21bdc7ce5577.png
题目解析
1. 状态体现：以i为结尾，dp是什么意思，是一共有多少种方法
2. 状态转移方程：以i位置最近的一步来划分题目
3. 初始化：dp = 1，dp = 2，dp = 4
4. 填表次序：从左向右填表
5. 返回值：返回dp的状态
https://i-blog.csdnimg.cn/direct/bbec8889fe9f46099e08382b058669e5.png
代码
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,dp = 2,dp = 4;
for(int i = 4;i <= n;i++)
{
dp = (((dp + dp) % k) + dp) % k;
}
return dp;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]