Day32--动态规划--509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯

方法：递归法

思路：

// 递归法
class Solution {public int fib(int n) {// 前两个数是初始化，无法通过递归得出if (n == 0 || n == 1) {return n;} else {// 公式递归return fib(n - 1) + fib(n - 2);}}
}

方法：动态规划

思路：

动态规划五步曲：

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

class Solution {public int fib(int n) {if (n == 0 || n == 1) {return n;}// 1.dp[i]指的是第i个数的斐波那契数值// 从0到n是有n+1个数值int[] dp = new int[n + 1];// 3.初始化dp[0] = 0;dp[1] = 1;// 4.遍历顺序，从前往后for (int i = 2; i <= n; i++) {// 2.递推公式dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

方法：动态规划

思路：

优化空间。其实只需要三个空间就可以完成了。

可以发现当计算完dp[i] = dp[i-1]+dp[i-2]之后，dp[i-2]就没用了。

此轮的dp[i-1]会变成下一轮的dp[i-2]，所以整个数组左移一位，动态覆盖就好。

// 动态规划（空间优化版）
class Solution {public int fib(int n) {if (n == 0 || n == 1) {return n;}int[] dp = new int[3];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {// 递推公式dp[2] = dp[0] + dp[1];// 计算完dp[2]之后，dp[0]就没用了，整体往前一个位置。dp[0] = dp[1];dp[1] = dp[2];}return dp[2];}
}

方法：递归，回溯

思路：

超时，太暴力了。时间复杂度是2^n，指数级别的，很恐怖。

// 回溯法（超时，太暴力了）
class Solution {int count = 0;int pathSum = 0;public int climbStairs(int n) {backtracking(n);return count;}private void backtracking(int n) {if (pathSum == n) {count++;return;}if (pathSum > n) {return;}// 每一轮选1或者2for (int i = 1; i <= 2; i++) {pathSum += i;backtracking(n);pathSum -= i;}}
}

方法：动态规划

思路：

1. 因为每一次可以走一步或者两步，当n是3的时候，肯定是从1或者2那里跳过来的
2. 所以1或者2有几种可能，3就是它俩的总和
3. 由此得出递推公式：dp[i] = dp[i-1]+ dp[i-2];（这不就是斐波那契数列吗？）

// 动态规划
class Solution {public int climbStairs(int n) {if (n == 1 || n == 2) {return n;}// 虽然从1到n只有n个数，但是0是无意义的，所以初始化要从1开始，数组长度要n+1int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

同样，这里可以进行空间优化，仅用3个空间。参考上一题的实现。不再赘述。

方法：动态规划

思路：

1. 这里可以理解为，跳了之后才收费。dp[i]看是从dp[i-1]跳上来的，还是dp[i-2]跳上来的，对应加上那个格子的cost[]
2. 注意：n+1才是楼顶，在索引n的地方

// 动态规划
// 这里可以理解为，跳了之后才收费。dp[i]看是从dp[i-1]跳上来的，还是dp[i-2]跳上来的，对应加上那个格子的cost[]
// 注意：n+1才是楼顶，在索引n的地方
class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];// 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0dp[0] = 0;dp[1] = 0;// 计算到达每一层台阶的最小费用for (int i = 2; i <= n; i++) {// dp是前面的跳到那个位置的累加和，因为是跳了之后才收费，所以要加上对应的cost[]dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
}

测试用例的dp[]情况：

n:3
cost:[10,15,20]
dp:[0,0,10,15]
index:[0,1,2,n]n:10
cost:[1,100,1,1,1,100,1,1,100,1]
dp:[0,0,1,2,2,3,3,4,4,5,6]
index:[0,1,2,3,4,5,6,7,8,9,n]
n+1才是楼顶，在索引n的地方