Skip to content

Latest commit

 

History

History
252 lines (185 loc) · 7.04 KB

0070.爬楼梯完全背包版本.md

File metadata and controls

252 lines (185 loc) · 7.04 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

70. 爬楼梯

力扣题目链接

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1: 输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2: 输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思路

之前讲这道题目的时候,因为还没有讲背包问题,所以就只是讲了一下爬楼梯最直接的动规方法(斐波那契)。

这次终于讲到了背包问题,我选择带录友们再爬一次楼梯!

这道题目 我们在动态规划:爬楼梯 中已经讲过一次了,原题其实是一道简单动规的题目。

既然这么简单为什么还要讲呢,其实本题稍加改动就是一道面试好题。

改为:一步一个台阶,两个台阶,三个台阶,.......,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢?

1阶,2阶,.... m阶就是物品,楼顶就是背包。

每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了!

和昨天的题目动态规划:377. 组合总和 Ⅳ基本就是一道题了。

动规五部曲分析如下:

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

dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法

  1. 确定递推公式

动态规划:494.目标和动态规划:518.零钱兑换II动态规划:377. 组合总和 Ⅳ中我们都讲过了,求装满背包有几种方法,递推公式一般都是dp[i] += dp[i - nums[j]];

本题呢,dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]

那么递推公式为:dp[i] += dp[i - j]

  1. dp数组如何初始化

既然递归公式是 dp[i] += dp[i - j],那么dp[0] 一定为1,dp[0]是递归中一切数值的基础所在,如果dp[0]是0的话,其他数值都是0了。

下标非0的dp[i]初始化为0,因为dp[i]是靠dp[i-j]累计上来的,dp[i]本身为0这样才不会影响结果

  1. 确定遍历顺序

这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不一样!

所以需将target放在外循环,将nums放在内循环。

每一步可以走多次,这是完全背包,内循环需要从前向后遍历。

  1. 举例来推导dp数组

介于本题和动态规划:377. 组合总和 Ⅳ几乎是一样的,这里我就不再重复举例了。

以上分析完毕,C++代码如下:

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        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 - j];
            }
        }
        return dp[n];
    }
};
  • 时间复杂度: O(nm)
  • 空间复杂度: O(n)

代码中m表示最多可以爬m个台阶,代码中把m改成2就是本题70.爬楼梯可以AC的代码了。

总结

本题看起来是一道简单题目,稍稍进阶一下其实就是一个完全背包!

如果我来面试的话,我就会先给候选人出一个 本题原题,看其表现,如果顺利写出来,进而在要求每次可以爬[1 - m]个台阶应该怎么写。

顺便再考察一下两个for循环的嵌套顺序,为什么target放外面,nums放里面。

这就能考察对背包问题本质的掌握程度,候选人是不是刷题背公式,一眼就看出来了。

这么一连套下来,如果候选人都能答出来,相信任何一位面试官都是非常满意的。

本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包,而且题目进阶的内容在leetcode上并没有原题,一定程度上就可以排除掉刷题党了,简直是面试题目的绝佳选择!

其他语言版本

Java:

class Solution {
    public int climbStairs(int n) {
        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) dp[i] += dp[i - j];
            }
        }

        return dp[n];
    }
}

Python3:

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n + 1)
        dp[0] = 1
        m = 2
        # 遍历背包
        for j in range(n + 1):
            # 遍历物品
            for step in range(1, m + 1):
                if j >= step:
                    dp[j] += dp[j - step]
        return dp[n]

Go:

func climbStairs(n int) int {
	//定义
	dp := make([]int, n+1)
	//初始化
	dp[0] = 1
	// 本题物品只有两个1,2
	m := 2
	// 遍历顺序
	for j := 1; j <= n; j++ {	//先遍历背包
		for i := 1; i <= m; i++ {	//再遍历物品
			if j >= i {
				dp[j] += dp[j-i]
			}
			//fmt.Println(dp)
		}
	}
	return dp[n]
}

JavaScript:

var climbStairs = function(n) {
    const dp = new Array(n + 1).fill(0);
    const m = 2;
    dp[0] = 1;
    for(let i = 1; i <= n; i++){
        for(let j = 1; j <= m; j++){
            if(i >= j) {
	    	dp[i] += dp[i - j];
	     }
        }
    }
    return dp[n];
};

TypeScript:

function climbStairs(n: number): number {
    const m: number = 2;    // 本题m为2
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    // 遍历背包
    for (let i = 1; i <= n; i++) {
        // 遍历物品
        for (let j = 1; j <= m; j++) {
            if (j <= i) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
};

Rust:

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        let (n, m) = (n as usize, 2);
        let mut dp = vec![0; n + 1];
        dp[0] = 1;
        for i in 1..=n {
            for j in 1..=m {
                if i >= j {
                    dp[i] += dp[i - j];
                }
            }
        }
        dp[n]
    }
}