1.理论基础

什么是动态规划

简称DP，dp里的每一个状态一定是由上一个状态推导出来的

解题步骤

确定dp数组及其下标的含义
确定递推公式
dp数组进行初始化
确定遍历顺序
推导dp数组

如何debug

这道题目我举例推导状态转移公式了么？

我打印dp数组的日志了么？

打印出来了dp数组和我想的一样么？

2.fib数列

509. 斐波那契数 - 力扣（LeetCode）

题意：

fib数列的含义为
$f [0] = 0, f [1] = 1; f [i] = f [i ? 1] + f [i ? 2] i > 1$
给出n，求f[n]

思路：

确定dp数组及其下标的含义：dp[i]表示第i项fib的值
确定递推公式：正如题意所说，递推公式为dp[i]=dp[i-1]+dp[i-2]
dp数组进行初始化：正如题意所说，dp[0]=0,dp[1]=1
确定遍历顺序：只有一层遍历
推导dp数组：答案就是dp[n]

代码：

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        int[] dp=new int[n+1];
        dp[0]=0;dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

3.爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

题意：

每次可以爬1或2个台阶，问有多少种不同的方法可以爬到第n个台阶

思路：

确定dp数组及其下标的含义：dp[i]表示爬到第i层的不同方法数量
确定递推公式：因为每次都可以爬1或2个台阶，也就是说如果当前爬到了第i层，那么上一次有可能爬1或2个台阶，所以前一个状态为dp[i-1]或dp[i-2]。因为统计的是不同方法的个数，所以递推公式为dp[i]=dp[i-1]+dp[i-2]
dp数组进行初始化：根据题意可知，dp[1]=1,dp[2]=2。其中后者的含义为想要爬到第2个台阶，可以先爬到第1个台阶再继续爬1个台阶，也可以直接爬2个台阶。dp[0]在本题里没有意义。
确定遍历顺序：只有一层循环
推导dp数组

代码：

时间复杂度和空间复杂度都是O(n)

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        int[] 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];
    }
}

拓展：

每次可以走[1,m]个台阶，问有多少种方法爬到第n个台阶？

相当于一个完全背包问题。

初始化为dp[0]=1，具体含义就是到达第0个台阶只有不走这一种方法。

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        int[] dp=new int[n+1];
        int m=2;
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i-j>=0)
                    dp[i]=dp[i]+dp[i-j];
            }
        }
        return dp[n];
    }
}

4.使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

题意：

cost[i]表示从楼梯第i个台阶向上爬需要支付的费用，支付此费用后可以选择向上爬1-2个台阶。可以选择从下标为0/1的台阶开始爬楼梯。计算到达第n个台阶的最低花费。

思路1：

确定dp数组及其下标的含义：dp[i]表示到达第i个台阶的最低花费（为了方便转移姑且认为第一步一定要花费，最后一步不用花费）
确定递推公式：dp[i]=min(dp[i-1],dp[i-2])+cost[i]，因为选的是最低花费，所以是对之前的两个状态取min。要加上cost[i]可以理解为支付了才能继续向上爬
dp数组进行初始化：dp[0]=cost[0],dp[1]=cost[1]
确定遍历顺序：一层循环
推导dp数组：返回结果是min(dp[n-1],dp[n-2])，因为实际上最后一步是没有花费的。

代码1：

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

思路2：

刚刚那种真的是太不好理解了。

确定dp数组及其下标的含义：dp[i]表示到达第i个台阶的最低花费（这里我们认为第一步不需要花费）
确定递推公式：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])，因为选的是最低花费，所以是对之前的两个状态取min。从i-1个台阶爬过来需要花费cost[i-1]，所以要加上对应的cost数组值。
dp数组进行初始化：dp[0]=0,dp[1]=0，这里初始化为0表示默认第一步是不花费体力的。
确定遍历顺序：一层循环
推导dp数组：返回结果是dp[n]

代码2：

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