数据结构和算法-动态规划（爬楼梯）

数据结构和算法-动态规划（爬楼梯）分别定位为求总和，求最值的问题

动态规划是特么什么鬼，为什么要爬楼梯。我坐电梯不行嘛。动态规划主要是解决什么问题，为什么要使用，怎么使用，对于什么状态转移方程，重叠子问题，base。定义明白，一遇到换个变种就束手无策了。这不叫明白，这叫自欺其人。

怎么使用动态规划解决求和问题

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

从题出发来看。我每次可以选择爬1个或者2个台阶，那么当我爬第一阶是我只有一种1种方式，那么我爬第2阶台阶，我就有2种方式，第3阶呢，我就会有3种方式分别是{[1,1,1],[1,2],[2,1]},那么我爬4阶呢我有多少种呢我会有{[1,1,1,1],[1,2,1],[2,1,1],[2,2],[1,1,2]}。那么这么穷举下去，当台阶等于N我就可以得到我总共有多少种方式来登顶，这显然是AC了。所以呢就需要去优化。我们发现登3阶依赖于登1阶和登2阶，每次爬1阶登顶对于结果的影响等于0，关键在于登1阶再登2阶，还是登2阶再等1阶。所以我们可以得到登台阶的数学方程式。f(n)=f(n-1)+f(n-2);这个也就是71题用来动态规划计算的状态方程。

明确了第一阶，第二阶的登顶的次数，这就是base。自底向上求解就是动态规划，而递归则是自顶向下求解。

 public int climbStairs(int N){
        if(N==0) return 0;
        if(N==1) return 1;
        if(N==2) return 2;
        int one=1;
        int two=2;
        int depth=0;
        for(int i=3;i<=N;i++){
            depth=one+two;
            one=two;
            two=depth;
        }
        return depth;
    }

咋老李也不会啥花里胡哨的玩意，就是穷举呗，找规律，转换思路，别被问题吓死了，找个本子写写，这是无状态求总和的。记住自底向上，想上天，你得把登天的梯子找到了登上去。

怎么使用动态规划解决求最值问题

746. 使用最小花费爬楼梯

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯.

示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

同样也是理解题意，你连题意都不知道做什么，那你怎么写对吧。根据题意会给你你爬每层楼要花费的力气。需要你计算爬到顶楼你最省劲的消耗是多少，哦还提示你可以从0阶或者1阶可以开始。同样也是我一次可以爬一个台阶或者2个台阶。当我爬楼梯的时候我不费力气所以是0，当我爬第一阶那么我需要的就是nums[0]的消耗，我爬2阶台阶的时候我要求最小花费Math.min(nums[0],nums[1])同理我就得到了爬第三个台阶的花费就是使用一次爬一阶楼梯到第2阶台阶的消耗加上登上第三阶的消耗和使用一次爬2阶到第1阶计算前2阶登到3阶所用的消耗** dp方程就是 dp[m]=Math.min((dp[i-1]+nums[i]),dp[i-2]+num[i-1])
上代码

 public int minCostClimbingStairs(int[] cost) {
        int[] dp=new int[cost.length];
        dp[0]=0;
        dp[1]=Math.min(cost[0],cost[1]);
        for(int i=2;i<cost.length;i++){
            dp[i]=Math.min(dp[i-1]+cost[i],dp[i-2]+cost[i-1]);
        }
        return dp[cost.length-1];
    }