动态规划（一）——斐波那契数列模型
文章目录
- 斐波那契数列模型
- 第N个泰波那契数
- 补充：空间优化——滚动数组
- 三步问题
- 最小花费爬楼梯
- 解码方法
斐波那契数列模型
回头总结：
斐波那契数列模型一般都是线性dp，对于这类DP题目的状态表示一般是 以i为结尾，…
分析状态转移方程时要特别注意：最近的一次状态，怎么转化过来的，几种情况
第N个泰波那契数
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
【五步分析】
-
状态表示
根据题目要求，易知
dp表的每个元素dp[i]为第 i 个泰波那契数 -
状态转移方程
题目给出：Tn+3 = Tn + Tn+1 + Tn+2，将该式化简得：Tn = Tn-3 + Tn-2 + Tn-1
所以状态转移方程为：
dp[i] = dp[i-3] + dp[i-2] + dp[i-1] -
初始化
初始化要保证不越界，根据状态转移方程可知
dp[0]、dp[1]、dp[2]需要初始化，初始化值题目给出另外还要处理边界情况，当题目所求的是第0、1个泰波那契数时，初始化
dp表可能会出现越界问题，我们要单独处理 -
填表顺序
从左往右，保证填写当前状态值时，所需状态值均计算过
-
返回值
根据题目要求和状态表示，可知返回值为
dp[n]。另外，由于泰波那契数从0开始，所以我们的dp表要申请 n+1 个空间。
【代码编写】
class Solution {public int tribonacci(int n) {if(n == 0) {return 0;}if(n == 1) {return 1;}//创建dp表int[] dp = new int[n + 1];//初始化dp[1] = dp[2] = 1;//填表for(int i = 3; i < dp.length; i++) {dp[i] = dp[i-3] + dp[i-2] + dp[i-1];}//返回值return dp[n];}
}
补充：空间优化——滚动数组
以第N个泰波那契数为例，填表时只需要当前状态的前三个状态的值，并且返回值也是最后填入的状态值，随着不断填表，前面的空间相当于浪费了，这时候采用滚动数组的思想进行空间优化：
public int tribonacci(int n) {if(n == 0) {return 0;}if(n == 1 || n == 2) {return 1;}//创建并初始化int a = 0,b = 1,c = 1,d = 0;//"填表"for(int i = 3; i <= n; i++) {d = a + b + c;a = b;b = c;c = d;}//返回值return d;}
三步问题
面试题 08.01. 三步问题 - 力扣（LeetCode）
【五步分析】
-
状态表示
根据经验，
dp[i]表示到达i位置时，方法总数 -
状态转移方程
由于到达
dp[i]位置可以选择走1步、2步或者3步，所以可以分三种情况：- 先到达
dp[i-1]的位置，然后走一步 - 先到达
dp[i-2]的位置，然后走两步 - 先到达
dp[i-3]的位置，然后走三步
所以状态转移方程为：
dp[i] = dp[i-3] + dp[i-2] + dp[i-1] - 先到达
-
初始化
dp[0]、dp[1]、dp[2]。同时，要处理边界情况。 -
填表顺序
从左往右，保证填写当前状态值时，所需状态值均计算过
-
返回值
返回值就是最后一个填表的状态值
dp[n-1]
【代码编写】
class Solution {public int waysToStep(int n) {if(n == 1) {return 1;}if(n == 2) {return 2;}//创建dp表int mod = (int)1e9 + 7;int[] dp = new int[n];//初始化dp[0] = 1;dp[1] = 2;dp[2] = 4;//填表for(int i = 3; i < dp.length; i++) {dp[i] = (((dp[i-1] + dp[i-2])%mod) + dp[i-3])%mod;}//返回值return dp[n-1];}
}
【分析时板书】
最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
【五步分析】
-
状态表示
根据经验+要求，
dp[i]表示到达i位置时的最小花费 -
状态转移方程
由于到达
dp[i]位置可以选择走1步或者2步，所以具体可以分两种情况：- 先到达
dp[i-1]的位置，然后支付cost[i-1]走一步，总花费：dp[i-1]+cost[i-1] - 先到达
dp[i-2]的位置，然后支付cost[i-2]走两步，总花费：dp[i-2]+cost[i-2]
由于要寻找最小花费，所以状态转移方程为：
dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]) - 先到达
-
初始化
dp[0]、dp[1]。同时，要处理边界情况。 -
填表顺序
从左往右，保证填写当前状态值时，所需状态值均计算过
-
返回值
返回值就是最后一个填表的状态值
dp[cost.length]，这是因为到达数组最后一个位置不算是到达楼顶，必须再到达下一个，也正因为如此dp表的长度为cost.length+1
【代码编写】
class Solution {public int minCostClimbingStairs(int[] cost) {//创建dp表int[] dp = new int[cost.length+1];//初始化dp[0] = dp[1] = 0;//填表for(int i = 2; i < dp.length; i++) {dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}//返回值return dp[cost.length];}
}
【分析时板书】
该题目的dp[i]也可以是从 i 位置开始，到达楼顶的最小花费，即将 i 位置作为起点而非终点，此时状态转移方程为：dp[i] = min(dp[i+1]+cost[i+1], dp[i+2]+cost[i+2])，此时填表顺序是从右往左，返回值则是min(dp[0], dp[1])
解码方法
91. 解码方法 - 力扣（LeetCode）
【五步分析】
-
状态表示
根据经验+要求，
dp[i]表示以 i 位置为结尾时，编码方法总数 -
★ 状态转移方程
分析
dp[i]的最近的一步：新加一个字符时，该字符可能可以单独编码；也可能和前一个字符结合编码，我们得讨论它们的可能性：
- 单独编码：‘0’不能单独编码，如果为’0’，则该字符单独编码情况下的方式为0；否则，就是
dp[i-1]种方式 - 结合编码：将这两个字符结合成一个数字，如果
10 <= 结合后的数字 <= 26（01、02…不能解码），则可以结合编码，结合后看作一个整体，所以方法有dp[i-2]种；否则，解码失败，方法数为0。
所以状态转移方程为：
dp[i] = dp[i-1](单独解码成功) + dp[i-2](结合编码成功) - 单独编码：‘0’不能单独编码，如果为’0’，则该字符单独编码情况下的方式为0；否则，就是
-
★ 初始化
易分析：
dp[0]、dp[1]需要初始化，字符串的第一个字符只要不为’0’，
dp[0] = 1；否则解码方式一定为0，可以直接return 0；第二个字符不为’0’，则
dp[1] = 2；否则，解码方式一定是0 -
填表顺序
从左往右，保证填写当前状态值时，所需状态值均计算过
-
返回值
返回值就是最后一个填表的状态值
dp[s.length()-1]
【代码编写】
class Solution {public int numDecodings(String s) {int c0 = Character.getNumericValue(s.charAt(0));if(c0 == 0) {return 0;}//创建dp表int[] dp = new int[s.length()];//初始化dp[0] = 1;if(s.length() == 1) {return dp[0];}int c1 = Character.getNumericValue(s.charAt(1));if(c1 != 0) {int tmp = c0 * 10 + c1;if(tmp <= 26 && tmp >= 10) {dp[1] = 2;}else {dp[1] = 1;}}else {if(c0 == 1 || c0 == 2) {dp[1] = 1;}else {return 0;}}//填表for(int i = 2; i < dp.length; i++) {int prev = Character.getNumericValue(s.charAt(i-1));int cur = Character.getNumericValue(s.charAt(i));int total = prev * 10 + cur;int dp1 = 0;int dp2 = 0;if(prev == 0 && cur == 0) {return 0;}else {//单独解码if(cur >= 1 && cur <= 9) {dp1 = dp[i-1];}if(total >= 10 && total <= 26) {dp2 = dp[i-2];}}dp[i] = dp1 + dp2;}return dp[s.length()-1];}
}
【分析时板书】
