很多时候不懂事

📝 题目描述 题目链接：最长有效括号 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 字串 的长度。 子字符串 是字符串中连续的字符序列。 左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。 示例： 12345678910111213141516示例 1：输入：s = "(()"输出：2解释：最长有效括号子串是 "()"示例 2：输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"示例 3：输入：s = ""输出：0 提示： 0 <= s.length <= 3 * 10^4 s[i] 为 '(' 或 ')' 💡 解题思路 方法一：动态规划 我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ) 结尾，因此我们可以知道以 ( 结尾的子串对应的 dp 值必定为 0...

📝 题目描述 题目链接：分割等和子集 给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例： 1234567891011示例 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 💡 解题思路 方法一：经典背包模板 先来回顾一下什么是传说中的背包问题：有 N 件物品和一个最多能容纳重量 W 的背包；第 i 件物品的重量是 weight[i]，价值是 value[i]；求解将哪些物品装入背包里物品价值总和最大；其中，如果每个物品能拿取无限多次，则叫作完全背包问题，若每个物品仅能拿取一次，则叫作01背包问题。 再来看这个题目，我们可以转化一下，先求出所有元素的和 sum，如果 sum 是偶数，我们令 target = sum/2...

📝 题目描述 题目链接：乘积最大子数组 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 请注意，一个只包含一个元素的数组的乘积是这个元素的值。 子数组 是数组中连续的 非空 元素序列。 示例： 1234567891011示例 1:输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 提示： 1 <= nums.length <= 2 * 10^4 -10 <= nums[i] <= 10 nums 的任何子数组的乘积都 保证 是一个 32-位 整数 💡 解题思路 方法一：动态规划 如果我们用 fmax​(i)f_{max}​(i)fmax​​(i) 开表示以第 iii 个元素结尾的乘积最大子数组的乘积，aaa 表示输入参数 numsnumsnums，那么根据“最大子...

📝 题目描述 题目链接：最长递增子序列 给你一个整数数组 nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 子序列 是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。 示例： 123456789101112131415示例 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 -10^4 <= nums[i] <= 10^4 💡 解题思路 方法一：动态规划 按照经典的动态规划模版，三步分析： 状态定义：设 dp[i] 表示以第 i 个数字结尾的最长递增子序列的长度。 初始状态：dp[i] ...

📝 题目描述 题目链接：单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例： 1234567891011121314151617示例 1：输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" &q...

📝 题目描述 题目链接：零钱兑换 给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 示例： 123456789101112131415示例 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] <= 2^31 - 1 0 <= amount <= 10^4 💡 解题思路 方法一：记忆化搜索（自顶向下的动态规划） 该问题可建模为以下优化问题： min⁡x ∑i=0n−1xisubject to ∑i=0n−1xi×ci=S\min_x \ {\textstyle \sum_{i=0...

📝 题目描述 题目链接：完全平方数 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例： 1234567891011示例 1：输入：n = 12输出：3 解释：12 = 4 + 4 + 4示例 2：输入：n = 13输出：2解释：13 = 4 + 9 提示： 1 <= n <= 10^4 💡 解题思路 方法一：动态规划 我们可以依据题目的要求写出状态表达式：f[i]f[i]f[i] 表示最少需要多少个数的平方来表示整数 iii。 这些数必然落在区间 [1,i][1,\sqrt{i}][1,i​]。我们可以枚举这些数，假设当前枚举到 jjj，那么我们还需要取若干数的平方，构成 i−j2i−j^2i−j2。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。 f[i]=1+j=min⁡j=1⌊i⌋f[i−j2]f[i]=1+j=\min_{j ...

📝 题目描述 题目链接：打家劫舍 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。 示例： 12345678910111213示例 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 💡 解题思路 方法一：动态规划 首先考虑最简单的情况。如果只有一间房屋，则偷窃该房...

📝 题目描述 题目链接：杨辉三角 给定一个非负整数 numRows，生成“杨辉三角”的前 numRows 行。 在 “杨辉三角” 中，每个数是它左上方和右上方的数的和。 示例： 123456789示例 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 💡 解题思路 方法一：动态规划 杨辉三角的每一行的每个数字，等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 nnn 行的第 iii 个数等于第 n−1n−1n−1 行的第 i−1i−1i−1 个数和第 iii 个数之和，状态转移方程为： dp[i][j]=dp[i−1][j−1]+dp[i−1][j]dp[i][j] = dp[i-1][j-1] + dp[i-1][j] dp[i][j]=dp[i−1][j−1]+dp[i−1][j] 🔧 代码实现 1、动态规划 1234567891011121314class S...

📝 题目描述 题目链接：爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例： 12345678910111213141516示例 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 💡 解题思路 方法一：动态规划 我们用 f(x)f(x)f(x) 表示爬到第 xxx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子： f(x)=f(x−1)+f(x−2)f(x)=f(x−1)+f(x−2) f(x)=f(x−1)+f(x−2) 它意味着爬到第 xxx 级台阶的方案数是爬到第 x−1x−1x−1 级台阶的方案数和爬到第 x−2x−2x−2 级台阶的方案数的和。很好理解，因为每次只能爬 111 级或 222 级，所以 f...