nineloong's blog

题目描述

118. 杨辉三角 (Easy)

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

70. 爬楼梯 (Easy)

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

示例：

输入: n = 3
输出: 3
解释: 三种方法分别是 (1,1,1)、(1,2)、(2,1)

求解思路：动态规划

两道题共享同一个核心思想——当前结果依赖于前面已计算的结果。

杨辉三角的递推关系直接从定义中来：第 i 行第 j 个数 = 上一行第 j-1 个数 + 上一行第 j 个数，即 dp(i)(j) = dp(i-1)(j-1) + dp(i-1)(j)。边界是每行的首尾元素恒为 1。这不难理解——杨辉三角的每一行完全由上一行决定，只需要逐行生成，每一行内部再按列填充即可。用二维列表逐层构造，代码几乎就是递推公式的直译。Python 代码中注释掉的那个版本则是另一种写法——先用列表推导式把每一行预填为全 1，然后从第三行起直接更新中间元素，好处是省去了每轮循环判断首尾的 if，代码更短。

爬楼梯则多了一步问题转化。从最终状态往回看，到达第 n 阶的最后一步只有两种可能：从第 n-1 阶迈 1 步上来，或者从第 n-2 阶迈 2 步上来。因此到达第 n 阶的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和：dp(n) = dp(n-1) + dp(n-2)。这正是斐波那契数列的递推式，只是初始值略有不同——dp(1) = 1，dp(2) = 2（两阶可以一次爬两步，也可以分两次各爬一步）。由于每个状态只依赖前两个，不需要维护完整的 DP 数组，用两个变量滚动更新就能把空间压到 O(1)。

解法：杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        for(int i = 0;i < numRows; i++){
            List<Integer> row = new ArrayList<>(i + 1);
            for(int j = 0; j <= i; j ++){
                if(j == 0 || j == i){
                    row.add(1);
                }
                else{
                    int val = dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j);
                    row.add(val);
                }
            }
            dp.add(row);
        }
        return dp;
    }
}

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        dp = []
        for i in range(numRows):
            row = []
            for j in range(i + 1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    val = dp[i - 1][j - 1] + dp[i - 1][j]
                    row.append(val)
            dp.append(row)
        return dp

复杂度： 时间 O(numRows²)，每个元素访问一次；空间 O(1) 不计返回结果。

解法：爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int first = 1;
        int second = 2;
        for(int i = 3; i <=n; i++){
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        first, second = 1, 2
        for _ in range(2, n):
            first, second = second, first + second
        return second

复杂度： 时间 O(n)，一次遍历；空间 O(1)，只用了三个变量。

Hot 100：杨辉三角 & 爬楼梯