java算法day38 | 动态规划part01 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

本文主要是介绍java算法day38 | 动态规划part01 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

理论基础

递归五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

509. 斐波那契数

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

1. 确定dp数组以及下标的含义
   dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式
   为什么这是一道非常简单的入门题目呢？
   因为题目已经把递推公式直接给我们了：
   状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3. dp数组如何初始化
   题目中把如何初始化也直接给我们了，如下：
   dp[0] = 0;
   dp[1] = 1;

4. 确定遍历顺序
   从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推导dp数组
   按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
   0 1 1 2 3 5 8 13 21 34 55

class Solution {public int fib(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]=1;for(int i=2;i<=n;i++){//第四步：去欸的那个遍历顺序dp[i]=dp[i-1]+dp[i-2];//第二部：确定递推公式} return dp[n];//第五步：举例推导dp数组}
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

70. 爬楼梯

思路和上一题很像，但要加上对于情景的联想。

class Solution {public int climbStairs(int n) {int[] dp=new int[n+1];//1.数组下标及含义：爬到第i层楼梯，有dp[i]种方法if(n==0 || n==1) return n;dp[1]=1;//3.dp数组初始化dp[2]=2;for(int i=3;i<=n;i++){//遍历顺序dp[i]=dp[i-1]+dp[i-2];//2.递推公式：dp[i] = dp[i - 1] + dp[i - 2] }return dp[n];}
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

746. 使用最小花费爬楼梯

思路： 这道题需要明确两个点：

1. 在初始位置上不动时花不花钱——不花，只有跳了才花
2. 什么是楼顶：下标位置为length的位置，而不是length-1；

class Solution {public int minCostClimbingStairs(int[] cost) {//1、数组的含义：登上第i阶台阶的累计最小花销int[] dp=new int[cost.length+1];//3、初始化数组dp[0]=0;dp[1]=0;//4、遍历顺序：从前往后for(int i=2;i<=cost.length;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//2、递推公式}return dp[cost.length];//5.举例推导dp数组}
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

这篇关于java算法day38 | 动态规划part01 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---