509.斐波那契数
题目：509. 斐波那契数 - 力扣（LeetCode）
思路：递归，遇到0，1，和小于0的数返回，
尝试（通过递归的方式AC）
class Solution {public int fib(int n) {if(n<0) return 0;if(n==0) return 0;if(n==1) return 1;int result = fib(n-1) + fib(n-2);return result;}
}答案
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.爬楼梯
题目：70. 爬楼梯 - 力扣（LeetCode）
思路：我要知道的是，有多少种相加的方式，我怎么知道所有方式都被穷尽了呢？实在想不到这个东西跟动态规划有什么关系，下一状态 = 上一状态 + 【1 或者 2】，想不通，每次填入dp[i]都有两种选择，1或者2，那我怎么计算次数？
答案
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];}
}小结
本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
- 牛的，卡尔的思路是总结规律得到的：把dp[i] 定义为 【爬到第i层楼梯，有dp[i]种方法】
如何可以推出dp[i]呢？
从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
- 注意，dp[0]在本题没有意义，不需要考虑第0层，直接从1和2开始就行
746.使用最小花费爬楼梯
题目：746. 使用最小花费爬楼梯 - 力扣（LeetCode）
思路：假设dp[i] 表示的是到了第i个台阶，需要的费用，那么dp[i]可以通过dp[i-1]再爬一个楼梯或者是dp[i-2]再爬两个楼梯得到，费用就是这些加上cost[i]，需要做的就是从两个里面选一个便宜的，如果两个费用相等，就选dp[i-2]
尝试（部分AC）
class Solution {public int minCostClimbingStairs(int[] cost) {if(cost.length == 3) return cost[1];int[] dp = new int[cost.length+1];dp[0] = cost[0];dp[1] = cost[1];for(int idx=2; idx<=cost.length-1; idx++){dp[idx] = Math.min(dp[idx-1],dp[idx-2])+cost[idx];}return dp[cost.length-1];}
}答案
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];}//最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
}小结
- 服了，就差最后一步的判断，要 return 【Math.min(dp[cost.length - 1], dp[cost.length - 2]);】
