文章目录
- 前言 : 动态规划简述
- 1 . 斐波那契模型
- 1.1 泰波那契数列
- 1.2 最小花费爬楼梯
- 1.3 解码方法
前言 : 动态规划简述
动态规划在当前我们的理解下,其实就是一种变相的递归,我们查看一些资料也可以知道,动态规划其实属于递归的一个分支,通过把递归问题开辟的栈帧通过一定的手段放到某一种"表"中去
动态规划标准解题流
在我们«数据结构与算法分析»中是这样描述动规的
在前一节，我们看到可以被数学上递归表示的问题也可以表示成一种递归算法，在许多情形下对朴素的穷举搜索得到显著的性能改进。
任何数学递推公式都可以直接转换成递归算法，但是基本现实是编译器常常不能正确对待退归算法，结果导致低效的程序。当怀疑很可能是这种情况时，我们必须再给编译器提供一些
分解
帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫作动 (dynamic programming)。
1 . 创建dp表(一维/二维数组)
2 . 确定我们的状态表示
---->方法是 经验+题目要求+分解为相同的子问题
---->目前已知的经验就是 以i位置为起点…/以i位置为末尾…
3 . 推导状态转移方程(相邻位置优先)
4 . 初始化(防止数组越界,处理边界位置)
5 . 填表,注意顺序(前 --> 后 / 后 --> 前)
6 . 返回值(这个跟你的开出来的dp表空间大小有关系)7 . 空间优化(这个不是主要的…其实能写出来就不错了)
1 . 斐波那契模型
1.1 泰波那契数列
关于本题的具体分析见下
public class Fibonacci {
/**
* 寻找第 n 个泰波那契数
*
* @param n --> 第几个数
* @return
*/
public int tribonacci(int n) {
创建dp表
int[] dp = new int[n + 1];
确定状态表示 --> 就是第几个泰波那契数
确定状态转移方程 --> dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]
初始化
if (n == 0 || n == 1) {
return n;
}
if (n == 2) {
return 1;
}
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
填表(顺序从左到右)
for (int i = 3; i < n + 1; ++i) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}
关于这个比较简单的题,我们还有一点要说的,请注意,这个dp表的空间是不是开的有点浪费,其实不难看出,我们真正需要的是三个临时遍历在相互赋值迭代,其实这也就是我们的空间优化的思路…
通过滚动数组来实现空间优化
上图是我们的空间优化可视化…
代码实现如下
class Solution {
public int tribonacci(int n) {
if(n == 0 || n == 1){
return n;
}
if(n == 2){
return 1;
}
int a = 0;
int b = 1;
int c = 1;
int d = 0;
for(int i = 3; i <= n; ++i){
d = a + b + c;
a = b;
b = c;
c = d;
}
return d;
}
}
1.2 最小花费爬楼梯
下面我们根据流程来分析一下这个题目
首先我们要明白的是那个位置是楼梯顶部…
这里的数组最后一个元素不是楼梯的顶端,最后一个元素的下一个才是
- 创建dp表,这里我们的dp表开n+1个大小
- 确定状态表示 —> dp[i] 表示到达i位置所需的最小花费
- 确定状态转移方程(下图可视化)
dp[i] = min(dp[i - 2] + cost[i - 2] , dp[i - 1] + cost[i - 1])- 初始化 0 和 1 位置
- 填表,顺序从左到右
- 返回值,返回dp[n]
下面是我们的代码实现
class Solution {
public int minCostClimbingStairs(int[] cost) {
//创建dp表
int[] dp = new int[cost.length + 1];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i < cost.length + 1; ++i){
dp[i] = Math.min(dp[i - 1]+cost[i - 1],dp[i - 2]+cost[i - 2]);
}
return dp[cost.length];
}
}
解法二其实就是从后向前遍历,题解如下
class Solution {
public int minCostClimbingStairs(int[] cost) {
//解法2,我们换一种dp的思路(dp[i]为从i位置为起点到终点的最小花费)
int len = cost.length;
//初始化就应该换成最后两个元素,然后从后往前遍历
int[] dp = new int[len];
dp[len - 1] = cost[len - 1];
dp[len - 2] = cost[len - 2];
for(int i = len - 3; i >= 0; --i){
dp[i] = Math.min(dp[i + 1],dp[i + 2]) + cost[i];
}
return Math.min(dp[0],dp[1]);
}
}
1.3 解码方法
本题分析如下
为什么能往动态规划上面想,其实我们每个解码都可以相互拆解,就有一种斐波那契的影子,所以很自然的向我们的动态规划上面去想
- 创建dp表
- 确定状态表示(dp[i]为解码到i位置的解码方法数目)
- 推导状态转移方程(见下图)
- 初始化 0 跟 1 位置
- 填表,顺序从左到右
- 输出返回值
class Solution {
public int numDecodings(String s) {
char[] chars = s.toCharArray();
//创建dp表
int[] dp = new int[s.length()];
//确定状态表示 --> 就是解码到n位置的方法总数
//确定状态转移方程(这个比较复杂)
//初始化
if (chars[0] != '0') {
dp[0] = 1;
}
if (s.length() == 1) {
return dp[0];
}
if (chars[1] >= '1' && chars[1] <= '9' && dp[0] != 0) {
dp[1] += 1;
}
if ((chars[0] - '0') * 10 + chars[1] - '0' >= 10 && (chars[0] - '0') * 10 + chars[1] - '0' <= 26) {
dp[1] += 1;
}
for (int i = 2; i < s.length(); ++i) {
if (chars[i] >= '1' && chars[i] <= '9') {
dp[i] += dp[i - 1];
}
if ((chars[i - 1] - '0') * 10 + chars[i] - '0' >= 10 && (chars[i - 1] - '0') * 10 + chars[i] - '0' <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[s.length() - 1];
}
}
本节会持续更新…
