題目

509、斐波那契數(shù)

斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始，后面的每一項數(shù)字都是前面兩項數(shù)字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 給你n ，請計算 F(n) 。

示例 1：

輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

輸入：4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：

0 <= n <= 30

class Solution {public int fib(int n) {if (n < 2) return n;int a = 0, b = 1, c = 0;for (int i = 1; i < n; i++) {c = a + b;a = b;b = c;}return c;}
}

//非壓縮狀態(tài)的版本
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 index = 2; index <= n; index++){dp[index] = dp[index - 1] + dp[index - 2];}return dp[n];}
}

70、爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1 階 + 1 階
2 階
示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階

// 常規(guī)方式
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];
}

// 用變量記錄代替數(shù)組
class Solution {public int climbStairs(int n) {if(n <= 2) return n;int a = 1, b = 2, sum = 0;for(int i = 3; i <= n; i++){sum = a + b;  // f(i - 1) + f(i - 2)a = b;        // 記錄f(i - 1)，即下一輪的f(i - 2)b = sum;      // 記錄f(i)，即下一輪的f(i - 1)}return b;}
}

746、使用最小花費爬樓梯

數(shù)組的每個下標作為一個階梯，第 i 個階梯對應著一個非負數(shù)的體力花費值 cost[i]（下標從 0 開始）。

每當你爬上一個階梯你都要花費對應的體力值，一旦支付了相應的體力值，你就可以選擇向上爬一個階梯或者爬兩個階梯。

請你找出達到樓層頂部的最低花費。在開始時，你可以選擇從下標為 0 或 1 的元素作為初始階梯。

示例 1：

輸入：cost = [10, 15, 20]
輸出：15
解釋：最低花費是從 cost[1] 開始，然后走兩步即可到階梯頂，一共花費 15 。
示例 2：

輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出：6
解釋：最低花費方式是從 cost[0] 開始，逐個經(jīng)過那些 1 ，跳過 cost[3] ，一共花費 6 。
提示：

cost 的長度范圍是 [2, 1000]。
cost[i] 將會是一個整型數(shù)據(jù)，范圍為 [0, 999] 。

// 方式一：第一步不支付費用
class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] dp = new int[len + 1];// 從下標為 0 或下標為 1 的臺階開始，因此支付費用為0dp[0] = 0;dp[1] = 0;// 計算到達每一層臺階的最小費用for (int i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[len];}
}

// 方式二：第一步支付費用
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length];dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < cost.length; i++) {dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];}//最后一步，如果是由倒數(shù)第二步爬，則最后一步的體力花費可以不用算return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
}