81、爬楼梯

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

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

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

思路解答：

到达第 i 阶楼梯的方法数等于到达前一阶（i-1）和前两阶（i-2）的方法数之和

def climbStairs(n: int) -> int:
    if n == 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]
 
 更简洁写法：
     def climbStairs(n: int) -> int:
        if n == 1:
        	return 1
        a, b = 1, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b

82、杨辉三角

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

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

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

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

思路解答：

1. 对于每一行 i，生成一个长度为 i+1 的列表 row，其中第一个和最后一个元素为 1。
2. 对于每一行的第 2 到倒数第 2 个位置，result[i][j] = result[i-1][j-1] + result[i-1][j]，即当前位置的值等于上一行对应位置和前一个位置的值之和。
3. 将生成的 row 加入 result 中。
4. 返回生成的 result。

def generate(numRows: int) -> list[list[int]]:

    result = []

    for i in range(numRows):
        row = [1] * (i + 1)
        if i > 1:
            for j in range(1, i):
                row[j] = result[i - 1][j-1] + row[i - 1][j]
        result.append(row)

    return result

83、打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路解答：

dp[i] 表示偷盗前 i 个房屋时能够获得的最大金额。

动态规划的转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，即在第 i 个房屋时，选择偷取当前房屋或者不偷取当前房屋，取两者的最大值作为当前的最优解。

最终返回 dp[-1] 即可得到最终结果。

def rob(nums: list[int]) -> int:

    if not nums:
        return 0

    if len(nums) == 1:
        return nums[0]

    # 初始化动态规划数组
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    # 动态规划过程
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

84、完全平方数

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

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

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

思路解答：

1. 初始化一个长度为 n+1 的数组 dp，其中 dp[i] 表示和为 i 的完全平方数的最少数量。
2. 对数组进行遍历，对于每个 i，初始化为一个较大的值，然后遍历所有小于等于 i 的完全平方数 j*j，更新 dp[i] = min(dp[i], dp[i-j*j]+1)。
3. 最终返回 dp[n] 即为所求的结果。

def numSquares(n: int) -> int:

    dp = [float('inf')] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        for j in range(1, int(math.sqrt(i)) + 1):
            dp[i] = min(dp[i], dp[i - j * j] + 1)

    return dp[n]

85、零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思路解答：

dp[i] 表示组成金额 i 所需的最少硬币个数。

初始时，除了金额为 0 的情况，其余金额的最少硬币个数都初始化为无穷大。然后遍历金额从 1 到 amount 的所有情况，对于每个金额，遍历所有硬币面额，更新最少硬币个数。

最终返回 dp[amount] 即可得到结果。

def coinChange(coins: list[int], amount: int) -> int:

    dp = [float('inf')] * (amount + 1)

    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

86、单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

思路解答：

dp[i] 表示字符串 s 的前 i 个字符是否可以被字典中的单词拼接而成。

初始时，空字符串可以被拼接而成，因此 dp[0] = True。然后遍历字符串 s 的所有子串，如果存在一个位置 j，使得 dp[j] 为 True 且子串 s[j:i] 在字典中，那么 dp[i] 也为 True。

最终返回 dp[n] 即可得到结果。

def  wordBreak(s: str, wordDict: list[str]) -> bool:

    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    wordSet = set(wordDict)

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break

    return dp[n]

87、最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

思路解答：

dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

初始时，每个元素自身构成一个长度为 1 的递增子序列。然后遍历数组，对于每个位置 i，再次遍历之前的位置 j，如果 nums[i] > nums[j]，则更新 dp[i] = max(dp[i], dp[j] + 1)，表示以第 i 个元素结尾的最长递增子序列长度为之前最长子序列长度加 1 或自身。

最终返回 dp 中的最大值即可得到结果。

def  lengthOfLIS(nums: list[int]) -> int:
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

88、乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32位 整数

思路解答：

max_num 表示以当前元素结尾的乘积最大子数组的乘积，min_num 表示以当前元素结尾的乘积最小子数组的乘积，result 表示全局最大乘积。

从数组的第二个元素开始遍历，对于每个元素，更新 max_num 和 min_num，同时更新 result 为全局最大值。在更新 max_num 和 min_num 的过程中，如果当前元素是负数，交换 max_num 和 min_num 的值，从而正确处理负数相乘的情况。

def maxmaxProduct(nums: list[int]) -> int:
    if not nums:
        return 0
    max_num, min_num, result = nums[0], nums[0], nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_num, min_num = min_num, max_num

        max_num = max(nums[i], max_num * nums[i])
        min_num = min(nums[i], min_num * nums[i])

        result = max(max_num, result)

    return result

89、分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

思路解答：

1. 首先计算整个数组的和 sum，如果 sum 是奇数，那么无法将数组分割成两个和相等的子集，直接返回 False。
2. 如果 sum 是偶数，那么我们需要找到一个子集，其和为 sum/2。这样，问题就转化为在数组中找到一个子集，使得子集的和为 sum/2。
3. 创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 个元素中能否找到一个子集，使得子集的和为 j。
4. 初始化 dp，将 dp[i][0]（表示在前 i 个元素中找到和为 0 的子集）设为 True。
5. 遍历数组 nums，对于每个元素 nums[i]，遍历可能的和 j（从 sum/2 到 nums[i]），更新 dp[i][j]。
6. 最终返回 dp [n][sum/2 的值。

def canPartition(nums: list[int]) -> bool:
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target = total_sum // 2
    n = len(nums)
    dp = [[False for _ in range(target + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True

    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

    return dp[n][target]

90、最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

思路解答：

1. 创建一个栈，用于存储括号的索引位置。
2. 初始化栈，将 -1 入栈，-1 的作用是用来计算有效括号子串的长度。
3. 遍历字符串，遇到 ‘(’ 就将其索引入栈，遇到 ‘)’ 就弹出栈顶元素。
4. 每次弹出栈顶元素时，计算当前有效子串的长度，更新最长有效子串的长度。
5. 最终栈中剩下的元素就是无法匹配的括号的索引，通过这些索引计算最长有效子串的长度。

def  longestlongestValidParentheses(s: str) -> int:

    stack = []
    stack.append(-1)
    max_length = 0

    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if len(stack) == 0:
                stack.append(i)
            else:
                max_length = max(max_length, i - stack[-1])

    return max_length