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];
}
}