day 38 ||第九章 动态规划part01||509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

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

509. 斐波那契数

首先我想的是递归方法，蒙对了，不过你自己对比一下你的递归和卡尔的递归，是不是还可以简化。。。。。

class Solution {public int fib(int n) {if(n==0) return 0;if(n == 1) return 1;int sum = recursion(n-1)+recursion(n-2);return sum;}private int recursion(int i){if(i == 0) return 0;if(i == 1) return 1;return recursion(i-1)+recursion(i-2);}
}

下面这是动态规划的方法：

class Solution {public int fib(int n) {if(n<=1) return n;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];}
}

70. 爬楼梯

我还是设置的dp[0]=1;

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

746. 使用最小花费爬楼梯

注意数组的大小定义，一定要是cost的长度加1，因为cost【i】是从第i个楼梯上去的消耗。

到最后访问dp数组的最后一个值，就是爬到楼顶所消耗的值。

class Solution {public int minCostClimbingStairs(int[] cost) {int dp[] = new int[cost.length+1];dp[0] = 0;dp[1] = 0;for(int i = 2;i<=cost.length;i++){dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.length];}
}

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

---