动态规划算法专题（一）：斐波那契数列模型

目录

1、动态规划简介

2、算法实战应用【leetcode】

2.1 题一：第N个泰波那契数

2.1.1 算法原理

2.1.2 算法代码

2.1.3 空间优化原理——滚动数组

2.1.4 算法代码——空间优化版本

2.2 题二：三步问题

 2.2.1 算法原理

2.2.2 算法代码

2.3 题二：使用最小花费爬楼梯

2.3.1 算法原理【解法一】

2.3.2 算法代码【解法一】

2.3.3 算法原理【解法二】

​2.3.4 算法代码【解法二】

2.4 题三：解码方法

2.4.1 算法原理

2.4.2 算法代码

2.4.3 初始化技巧

2.4.4 算法代码——初始化技巧使用

---

1、动态规划简介

‌动态规划（Dynamic Programming, DP）是运筹学的一个分支，用于求解最优化问题。

在解决问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法(自底向上)正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

动态规划算法，一般包含以下几个主要步骤:

1. 状态表示：dp表中的值所表示的含义。一般由 经验+题目要求 得出。对于一维的dp表，dp[i]通常有这两种表示形式(由经验得出)：①：以i位置为结尾，......；②：以i位置为起点，......；而....就是需要结合题目来得出的。
2. 状态转移方程：就是dp[i]是怎么来的。dp[i]通常由其相邻的其他状态经过公式计算得出，状态转移方程就是这个公式。
3. 初始化：确保在填dp表的过程中不越界。
4. 填表顺序：为了在填写当前状态的时候，所需要的其他相邻状态已经计算得出了。
5. 返回值：结合题目要求。

在此过程中，我认为确定状态表示是最重要的一点，而确定状态转移方程是最难的一点。 

2、算法实战应用【leetcode】

2.1 题一：第N个泰波那契数

. - 力扣（LeetCode）

2.1.1 算法原理

对于一维dp，状态表示通常由 经验+题目要求 得出，本题很明显，表示第i个泰波那契数的值；同时状态转移方程题目也是贴心的给出了。

• 状态表示dp[i]：第i个泰波那契数的值
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
• 初始化：dp[0] = 0; dp[1] = dp[2] = 1；
• 填表顺序：从左往右
• 返回值：dp[n]

2.1.2 算法代码

class Solution {public int tribonacci(int n) {if(n == 0) return 0;if(n == 1 || n == 2) return 1;int[] dp = new int[n + 1];dp[0] = 0; dp[1] = dp[2] = 1;for(int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];}
}

2.1.3 空间优化原理——滚动数组

实际上，我们可以不用创建一个dp数组来存储数值，

通过“滚动数组”的方式，进行空间优化。

仅仅使用三个变量就可以解题，不必再开辟额外的空间。

​

2.1.4 算法代码——空间优化版本

class Solution {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;}
}

---

2.2 题二：三步问题

. - 力扣（LeetCode）

 2.2.1 算法原理

• 状态表示(经验+题目要求)：dp[i]：到达第i个位置，一共有多少种方式
• 状态转移方程：要到达i位置，可由移动到i-1/i-2/i-3位置的基础上，再移动三/二/一步就可到达，即：dp[i]=dp[i-1]+dp[i-2]+dp[i-3]；
• 初始化：dp[1]=1; dp[2]=2; dp[3]=4;
• 填表顺序：从左往右

​

2.2.2 算法代码

class Solution {//dp[i]状态表示：到达i位置，一共有多少种方法public int waysToStep(int n) {//1e9 + 7：double类型int MOD = (int)1e9 + 7;if(n == 1 || n == 2) return n;int[] dp = new int[n + 1];//初始化dp[1] = 1; dp[2] = 2; dp[3] = 4;for(int i = 4; i < n + 1; i++) {//状态转移方程dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}return dp[n];}
}

---

2.3 题二：使用最小花费爬楼梯

. - 力扣（LeetCode）

2.3.1 算法原理【解法一】

• 状态表示dp[i]：到达i位置，最小花费的金额(以i位置为结尾)
• 状态转移方程：需要考虑，到达i-1位置和到达i-2位置最小花费的金额数，考虑完后，再进一步到达i位置。也就是说：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
• 初始化：dp[0]=0; dp[1]=0;（防越界）
• dp的建表顺序：从左至右
• 返回值：dp[n]

​

2.3.2 算法代码【解法一】

class Solution {public int minCostClimbingStairs(int[] cost) {//解法一：int n = cost.length;//状态表示dp[i]：到达i位置时，最小花费int[] dp = new int[n + 1];//初始化dp[0] = dp[1] = 0;//填表顺序：从左往右for(int i = 2; i <= n; i++) {//状态转移方程dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] +cost[i - 2]);}//返回值:dp[n]return dp[n];}
}

2.3.3 算法原理【解法二】

• 状态表示dp[i]：从i位置开始，到达楼顶，最小花费的金额(以i位置为起点)
• 状态转移方程：需要考虑，i+1位置和i+2位置到达楼顶最小花费的金额数，再选择走一步还是走两步。也就是说：dp[i]=min(cost[i-1],dp[i-2])+cost[i];
• 初始化：dp[i-1]=cost[i-1]; dp[i-2]=cost[i-2];（防越界）
• dp的建表顺序：从右至左
• 返回值：min(dp[0],dp[1])

​2.3.4 算法代码【解法二】

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;//状态表示dp[i]：以i位置为起点，到达楼顶的最小花费int[] dp = new int[n];//初始化dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];for(int i = n - 3; i >= 0; i--) {//填表顺序 -> 从右往左//状态转移方程 --> 自身花费+后面俩台阶的最小花费dp[i] = cost[i] +Math.min(dp[i + 1], dp[i + 2]);}//返回值，考虑 从第一个台阶出发 or 从第二个台阶出发return Math.min(dp[0], dp[1]);}
}

---

2.4 题三：解码方法

. - 力扣（LeetCode）

2.4.1 算法原理

• 状态表示dp[i]：以i位置为结尾，解码方式的总数
• 状态转移方程：s[i]单独解码(成功/失败)+s[i]/s[i-1]组合解码(成功/失败)：dp[i]=dp[i-1]+dp[i-2];
• 初始化：①：if(s[0]!='0') dp[0]=1; ②：dp[1] -->1. s[1]单独解码 & 2. s[1]与s[0]组合解码
• 返回值：dp[n-1]

​

2.4.2 算法代码

class Solution {public int numDecodings(String s) {int n = s.length();char[] c = s.toCharArray();//状态表示dp[i]：以i位置为结尾，解码方式的总数int[] dp = new int[n];//初始化第一个位置if(c[0] != '0') dp[0]++;//当长度为1时if(n == 1) return dp[0];//初始化第二个位置if(c[0] != '0' && c[1] != '0') dp[1]++;//单独编码int t = ((c[0] - '0') * 10 + (c[1] - '0'));if(t >= 10 && t <= 26) dp[1]++;//组合编码for(int i = 2; i < n; i++) {//单独编码if(c[i] != '0') dp[i] += dp[i - 1];//组合编码int tt = ((c[i - 1] - '0') * 10 + (c[i] - '0'));if(tt >= 10 && tt <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
}

2.4.3 初始化技巧

在编写代码时，我们发现了一个问题， 我们在完成初始化工作时，非常的麻烦，初始化的代码占据了大量的篇幅，此时，我们可以使用初始化技巧 ---> dp数组在创建时多开辟一个节点。将初始化时的代码放进循环中(将要初始化的节点与普通节点一概而论)，在填dp表的时候完成初始化。

不过，因为多开辟了一个位置，所以在循环填dp表时也需要注意以下问题：

1. 与原数组的下标映射关系发生了改变
2. 注意虚拟节点的值(多开辟的那一个节点)，虚拟节点的值，要保证后面计算得到的结果是正确的。

在本题中，虚拟节点dp[0]的值应该为1；

原因：

当s[1]可与s[0]组合解码时，会这样计算：dp[2]+=d[2-2](s中的i为1，映射到新dp中i为2)
因为能够组合解码，所以虚拟节点dp[0]的值应为1

​

2.4.4 算法代码——初始化技巧使用

class Solution {public int numDecodings(String s) {//初始化技巧 --> 优化int n = s.length();char[] c = s.toCharArray();//状态表示dp[i + 1]：以i位置为结尾，解码方式的总数int[] dp = new int[n + 1];//处理虚拟节点里的值dp[0] = 1;//初始化第一个位置if(c[0] != '0') dp[1]++;for(int i = 2; i < n + 1; i++) {//单独编码if(c[i - 1] != '0') dp[i] += dp[i - 1];//组合编码int t = ((c[i - 1 - 1] - '0') * 10 + (c[i - 1] - '0'));if(t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n];}
}

---

END