算法题记录 36

70.爬楼梯（简单）

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

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

涉及知识点

动态规划

解决思路

最基本的动态规划

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dfs(n:int)->None:
            if n<=1:
                return 1
            return dfs(n-2)+dfs(n-1)
        return dfs(n)

118.杨辉三角（简单）

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

涉及知识点

动态规划

解决思路

要递归也可以，但是不用这么麻烦，直接循环遍历即可。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        c = [[1] * (i + 1) for i in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, i):
                # 左上方的数 + 正上方的数
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
        return c

198.打家劫舍（中等）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

涉及知识点

动态规划

解决思路

基本的动态规划

class Solution:
    def rob(self, nums: List[int]) -> int:
        l=len(nums)
        @cache
        def dfs(n:int)->None:
            if n>l-1:
                return 0
            return max(dfs(n+1),dfs(n+2)+nums[n])
        return dfs(0)

279.完全平方数（中等）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

涉及知识点

动态规划

解决思路

基本的动态规划

# 写在外面，多个测试数据之间可以共享，减少计算量
@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
    if i == 0:
        return inf if j else 0
    if j < i * i:
        return dfs(i - 1, j)  # 只能不选
    return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return dfs(isqrt(n), n)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。