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

第一题：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 的台阶开始，因此支付费用为0         dp[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.length         for (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;     } }