动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

第一题：509. Fibonacci Number

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

//非压缩状态的版本
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. Climbing Stairs 

这题和第一题的斐波那契数是差不多的。

// 常规方式
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];
}

// 用变量记录代替数组
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. Min Cost Climbing Stairs 

// 方式一：第一步不支付费用
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];}//最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
}

// 状态压缩，使用三个变量来代替数组
class Solution {public int minCostClimbingStairs(int[] cost) {// 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;// 前两个台阶不需要费用就能上到，因此从下标2开始；因为最后一个台阶需要跨越，所以需要遍历到cost.lengthfor (int i = 2; i <= cost.length; i ++) {// 此处遍历的是cost[i - 1]，不会越界currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]);beforeTwoCost = beforeOneCost;beforeOneCost = currentCost;}return currentCost;}
}