「算法刷题」动态规划算法的楼梯和路径问题

本博客是记录作者做动态规划算法的简单和中等难度的基础题的笔记。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

LeetCode题目	相关题目类型	题目类型分析	题目思路	相关链接
509	斐波那契数（简单难度）	当前的数等于前两个数之和，求第n个数	f(n)=f(n-2)+f(n-1)	https://leetcode-cn.com/problems/fibonacci-number/
70	爬楼梯（简单难度）	第n个台阶只能从第n-1或者n-2个上来	到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法	https://leetcode-cn.com/problems/climbing-stairs/
746	使用最小花费爬楼梯（简单难度）	多爬一个台阶	假设这个cost共有N个台阶，则人需要爬到第i=N个台阶（假设cost[N]=0）才算结束，则其只能是从第N-1个台阶或者第N-2个台阶上爬上来的，并且需要支付cost[N]，若每个dp[i]表示达到第i个台阶花费的最小体力	https://leetcode-cn.com/problems/min-cost-climbing-stairs/
62	不同路径（中等难度）	二维版本的爬楼梯	dp[i][j]表示[0,0]到[i,j]需要多少条路径；第一行的每个位置都只有一条路径，第一列的每个位置都只有一条路径	https://leetcode-cn.com/problems/unique-paths/
63	不同路径II（中等难度）			https://leetcode-cn.com/problems/unique-paths-ii/

509 斐波那契数

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

1、确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2、确定递推公式

题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

3、dp数组如何初始化

dp[0] = 0;
dp[1] = 1;

4、确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5、举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

以上我们用动规的方法分析完了，C++代码如下：

int fib(int n) {
        /*输入一个整数，输出一个整数*/
        if(n<=1){
            return n;
        }
        vector<int> dp(n+1); //第i个数的斐波那契数值是dp[i]
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            dp[i] =  dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。代码如下：

int fib(int n) {
        /*输入一个整数，输出一个整数*/
        if(n<=1){
            return n;
        }
        vector<int> dp(2); //第i个数的斐波那契数值是dp[i]
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            int temp = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return dp[1];
    }

70 爬楼梯

这道题目的关键是明白第n个台阶只能从第n-1或者n-2个上来，所以到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法。

	int climbStairs(int n) {
        /*输入一个整数，输出一个整数*/
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        vector<int> dp={0,0,0};//爬到第i层楼梯，有dp[i]种方法
        dp[1] = 1;
        dp[2] = 2;
        // 第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法
        for(int i=3;i<n+1;i++){
            dp[0]=dp[1]+dp[2];
            dp[1] = dp[2];
            dp[2] = dp[0];
        }
        return dp[2];
    }

746 使用最小花费爬楼梯

这道题要注意在楼梯上停留时需要支付体力值。例如[10,15,20]

爬完楼梯指的是人走到20的后一个，而不是走到20就算爬完，在这个案例中其至少需要站在i=1的台阶上，所以必然花费15。

假设这个cost共有N个台阶，则人需要爬到第i=N个台阶（假设cost[N]=0）才算结束，则其只能是从第N-1个台阶或者第N-2个台阶上爬上来的，并且需要支付cost[N]，若每个dp[i]表示达到第i个台阶花费的最小体力

则dp[N]=min(dp[N-1]，dp[N-2])+cost[N]。

整理后的代码如下：

int minCostClimbingStairs(vector<int>& cost) {
        /*输入一个整型数组，输出一个数组
        思路：第i个台阶的最低体力=min(第i-1个台阶的最低体力，第i-2个台阶的最低体力)+cost[i],
        爬到第 cost.size()个台阶才算爬完，设cost[cost.size()]=0
        */
        int N = cost.size();
        vector<int> dp(N+1);// 每个dp[i]表示达到第i个台阶花费的最小体力
        dp[0]=cost[0];// 就一个台阶，只需要支付其体力就行
        dp[1]=cost[1];// 两个台阶，但是cost[1]必须支付，所以直接从1出发
        for(int i=2;i<=N;i++){
            if(i!=N){
                dp[i] = min(dp[i-1], dp[i-2])+cost[i];
            }else{
                dp[i] = min(dp[i-1], dp[i-2]);
            }
        }
        return dp[N];//最后一步不需要花费
    }

则另一个版本的代码如下：

int minCostClimbingStairs(vector<int>& cost) {
        /*输入一个整型数组，输出一个数组
        思路：第i个楼梯的最低体力=min(第i-1个楼梯的最低体力，第i-2个楼梯的最低体力)+cost[i]
        */
        vector<int> dp={0,0};// 每个dp[i]表示达到第i个台阶花费的最小体力
        dp[0]=cost[0];// 就一个台阶，只需要支付其体力就行
        dp[1]=cost[1];// 两个台阶，但是cost[1]必须支付，所以直接从1出发
        for(int i=2;i<cost.size();i++){
            int temp = min(dp[0], dp[1])+cost[i];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return min(dp[0],dp[1]);//最后一步不需要花费
    }

62 不同路径

int uniquePaths(int m, int n) {
        /*输入两个整数，输出一个整数
        思路：二维版本的爬楼梯，dp[i][j]=dp[i][j-1]+dp[i-1][j]
        */
        vector<vector<int>> dp(m, vector<int>(n, 0));//dp[i][j]表示[0,0]到[i,j]需要多少条路径
        //初始化数组
        for(int i=0;i<m;i++) dp[i][0]=1;//第一行的每个位置都只有一条路径
        for(int j=0;j<n;j++) dp[0][j]=1;//第一列的每个位置都只有一条路径
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }

63 不同路径II

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        /*输入一个二维数组，输出一个整数*/
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int> (n,0));
        // 初始化数组
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]!=1){
                dp[i][0]=1;
            }
            else{
                break;
            }
        }
        for(int j=0;j<n;j++){
            if(obstacleGrid[0][j]!=1){
                dp[0][j]=1;
            }
            else{
                break;
            }
        }
        // 推导dp数组
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]!=1){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }