一. 什么是动态规划
dp一般是需要前面状态的值的问题。比如,解决一个问题需要很多步骤,且步骤之间相关联,后一个步骤的推导需要前一个步骤的结论。而我们所做的就是,将这个带求解的问题分成若干步骤,将每个步骤答案保存,后面需要直接用即可。
二. 斐波那契数列
这类问题一般都是根据前面的状态值推导出当前的状态值
举个例子: 三步问题
题目描述: 有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
题目解析: 初始给出的迈楼梯级数是: 一次可以迈1级,2级,3级:
如果有1级台阶,可以一次迈1级上去,结果就是1种上楼梯实现方式;如果有2级台阶,可以一次迈2级/两次迈1级,结果就是2种上楼梯实现方式;同理3级,可以一次迈3级/迈1级再迈2级/迈2级再迈1级/三次迈1级,结果就是4种上楼梯实现方式
设置函数: 我们设置一个dp函数,使dp[i] 存储的是i级台阶时有几种迈步方法 -》根据我们之前推导出的状态 dp[1] = 1, dp[2] = 2, dp[3] = 4
函数转移方程:那进行推导第4阶台阶应该怎么算? 我们可以先思考4阶台阶是怎么迈过来的?他可以是从3阶台阶迈1步到4阶也就是-》4-1 -》 在计算3阶台阶的方法,也就是我们初始化的 dp[3] = 4;也可以是2阶台阶迈2步到4阶也就是4-2 在计算2阶台阶的方法....所以,dp[4] = dp[3]+dp[2]+dp[1] -> dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
临界值和初始化:需要初始化的就是dp的1,2,3 -》dp的长度设置为n+1; 而函数转移方程最小到i-3-》i需要从4开始
注意:对结果模1000000007-》每两个值相加后记得对结果模1000000007