【D13】最小路径和 & 爬楼梯 （LC 64&70）

64. 最小路径和

问题描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

解题思路

dp数组定义：dp[i][j]表示从左上角到达第i-1行、第j-1列的最小路径和
base case：到达左上角第一个格子的最小路径和为该格子本身的值
状态转移：1）若为第1行/列的格子，只有一条路径到达，最小路径和为经过的格子的累加值；2）若为中间的格子，可以先到达相邻上方的格子，再向下一格；也可以先到达相邻左侧的格子，再向右一格。最小路径和为这两个路径中较小的值加上当前格子的值；

代码实现

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        //dp[i][j]表示从左上角到达第i-1行、第j-1列的最小路径和
        int[][] dp = new int[m][n];
        //base case
        dp[0][0] = grid[0][0];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0){
                    if(i == 0 && j !=0){
                        //要达到第一行的网格，只能向右移动，最小路径和为经过的网格数字之和
                        dp[i][j] = dp[i][j-1] + grid[i][j];
                    }
                    if(j == 0 && i != 0){
                       //要达到第一列的网格，只能向下移动，最小路径和为经过的网格数字之和
                       dp[i][j] = dp[i-1][j] + grid[i][j]; 
                    }
                    continue;
                }
                //其余各自的最小路径和，取到达相邻上方格子、相邻左侧格子中较小的值加上当前格子数字
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j-1]) +grid[i][j] ;
            }
        }
        return dp[m-1][n-1];
    }
}

70. 爬楼梯

问题描述

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

解题思路

到达第n阶的方法有两种：1）先到第n-1阶，然后再爬1阶；2）先到n-2阶，然后再爬2阶。所以这题其实就是求斐波那契数列和

代码实现-递归

class Solution {
    public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

递归方法，提交的时候超过时间限制了=.=

代码实现-空间压缩后的动态规划

class Solution {
    public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        int m1 = 1, m2 = 2;
        for(int i = 3; i <= n; i++){
            int sum = m1 + m2;
            m1 = m2;
            m2 = sum;
        }
        return m2;
    }
}