建行网站网址,苏州建站网站模板,宝安三网合一网站建设,263企业邮箱 登陆文章目录 动态规划三步问题题目解析代码 动态规划 1. 状态表示#xff1a;dp[i]#xff0c;表示dp表中i下标位置的值 2. 状态转移方程#xff1a;以i位置位置的状态#xff0c;最近的一步来划分问题#xff0c;比如可以将状态拆分成前状态来表示现状态#xff0c;dp[i] … 文章目录 动态规划三步问题题目解析代码 动态规划 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] 1dp[2] 2dp[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;vectorint dp(n1);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];}
};
