斐波那契数，通常表示为 F(n)，形成一个序列，称为斐波那契数列，其中每个数都是前两个数的和，从 0 和 1 开始。即，
F(0) = 0, F(1) = 1
F(n)=F(n-1)+F(n-2)，对于n＞1 1.
给定 n，计算 F(n)。
示例1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
限制：
0 原始页面
public int fib(int n) {
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
else{
return fib(n-1) + fib(n-2);
}
}
递归法就像DFS一样，深入进行，然后回溯得到最终答案。
时间：O(2^n)
空间：O(1)
private int[] dp = new int[31];
public int fib(int n) {
if(n<2){
dp[n] = n;
return n;
}
if(n>=2 && dp[n]!=0){
return dp[n];
}
dp[n] = fib(n-1) + fib(n-2);
return dp[n];
}
我们可以使用全局数组来保存结果，以避免相同元素的重复递归。例如下图显示 f(17) 和 f(18) 是两种不同的递归路线，如果我们使用正常的递归方法，我们必须多次计算它们。
时间：O(n)，空间：O(n)
public int fib(int n) {
if(n<2){
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];
}
递归是从上到下再回溯，内存递归会保存递归结果，避免重复计算。现在动态规划从下到上进行，并将每一步的结果保存到 dp 数组中。
时间：O(n)
空间：O(n)
public int fib(int n) {
if(n<2){
return n;
}
int start = 0;
int pre = 1;
int res = pre;
for(int i=2; i<=n; i++){
res = start + pre;
start = pre;
pre = res;
}
return res;
}
您正在爬楼梯。需要n步才能到达山顶。
每次您可以爬 1 或 2 级台阶。您可以通过多少种不同的方式登上顶峰？
示例1：
输入：n = 2
输出：2
说明：有两种方法可以登顶。
输入：n = 3
输出：3
说明：共有三种方法可以登顶。
您正在爬楼梯。需要n步才能到达山顶。
每次您可以爬 1 或 2 级台阶。您可以通过多少种不同的方式登上顶峰？
示例1：
输入：n = 2
输出：2
说明：有两种方法可以登顶。
输入：n = 3
输出：3
说明：共有三种方法可以登顶。
限制：
1 原始页面
public int climbStairs(int n) {
if(n<3){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
if(n<3){
return n;
}
int prepre = 1;
int pre = 2;
int res = 0;
for(int i=3; i<=n; i++){
res = prepre + pre;
prepre = pre;
pre = res;
}
return res;
}
给定一个整数数组 cost，其中 cost[i] 是楼梯上第 i 步的成本。支付费用后，您可以爬一层或两层台阶。
您可以从索引 0 的步骤开始，也可以从索引 1 的步骤开始。
返回到达楼层顶部的最低成本。
示例1：
输入：成本 = [10,15,20]
输出：15
说明：您将从索引 1 开始。
输入：成本 = [1,100,1,1,1,100,1,1,100,1]
输出：6
说明：您将从索引 0 开始。
限制：
2
0
原始页面
public int minCostClimbingStairs(int[] cost) {
if(cost.length < 2){
return 0;
}
int[] dp = new int[cost.length+1];
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<dp.length; i++){
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[dp.length-1];
}
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`
以上是LeetCode Day动态编程第1部分的详细内容。更多信息请关注PHP中文网其他相关文章！
