动态规划刷题

动态规划

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

题目解析

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

代码

1. class Solution
2. {
3. public:
4.     int waysToStep(int n)
5.     {
6.         if(n == 1 || n == 2) return n;
7.         else if(n == 3) return 4;
8.         
9.         long long k = 1e9 + 7;
11.         vector<int> dp(n+1);
12.         dp[1] = 1,dp[2] = 2,dp[3] = 4;
13.         for(int i = 4;i <= n;i++)
14.         {
15.             dp[i] = (((dp[i-1] + dp[i-2]) % k) + dp[i-3]) % k;
16.         }
18.         return dp[n];
19.     }
20. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。