lthero

LeetCodeCampsDay45动态规划part12 下面几个子序列的题目都需要使用二维dp，而且关于两个字符串删除问题 并且都需要扩展dp的大小为dp(len(t1)+1, len(t2)+1)，第一行、第一列往往需要填充 所有涉及到两个字符串的dp问题，都有相似的状态转移过程 其中text1[i - 1] == text2[j - 1]，dp[i][j] 以及text1[i - 1] != text2[j - 1]，dp[i][j] 而dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]三种状态转移过来，只要能找到不同条件下状态转移的过程就好解决了 115. 不同的子序列 https://leetcode.cn/problems/distinct-subsequences/ 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。 测试用例保证结果在 32 位有符号整数范围内。 示例 1： 1234567输入：s = "rabbbit", t = "rabbit&qu ...

LeetCodeCampsDay44动态规划part11 下面几个子序列的题目都需要使用二维dp，一个维度给text1另一个给text2 并且都需要扩展dp的大小为dp(len(t1)+1, len(t2)+1)，第一行、第一列往往需要填充 所有涉及到两个字符串的dp问题，都有相似的状态转移过程 其中text1[i - 1] == text2[j - 1]，dp[i][j] 以及text1[i - 1] != text2[j - 1]，dp[i][j] 而dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]三种状态转移过来，只要能找到不同条件下状态转移的过程就好解决了 1143. 最长公共子序列 https://leetcode.cn/problems/longest-common-subsequence/ 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某 ...

LeetCodeCampsDay43动态规划part10 使用动态规划解决子序列问题 非连续子序列可以看成模板，而连续子序列只是非连续子序列的特例 最长重复子序列需要使用二维dp（每个维度对应一个数组序列） 300. 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 12输入：nums = [0,1,0,3,2,3]输出：4 示例 3： 12输入：nums = [7,7,7,7,7,7,7]输出：1 提示： 1 <= nums.length <= 2500 -104 <= nums[i] ...

LeetCodeCampsDay42动态规划part09 买卖股票的另类问题 309. 买卖股票的最佳时机含冷冻期 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 123输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 示例 2: 12输入: prices = [1]输出: 0 提示： 1 <= prices.length <= 5000 0 <= prices[i] <= 1000 动态规划思路 dp定义与含义 根据状态转移图 ...

LeetCodeCampsDay41动态规划part08 股票问题从入门到通关 121. 买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 1234输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 123输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= pric ...

LeetCodeCampsDay39动态规划part07 198. 打家劫舍 https://leetcode.cn/problems/house-robber/ 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 1234输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2： 1234输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 提示： 1 <= nums.length <= 100 0 <= nums[i] ...

LeetCodeCampsDay38动态规划part06 最小个数问题：零钱兑换、完全平方数 求排列问题：单词拆分 322. 零钱兑换 https://leetcode.cn/problems/coin-change/ 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1 示例 2： 12输入：coins = [2], amount = 3输出：-1 示例 3： 12输入：coins = [1], amount = 0输出：0 提示： 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104 动态规划思路 完全背包、装满到target的最小物品数量的问题 ...

LeetCodeCampsDay37动态规划part05 完全背包问题 完全背包 01背包：每个物品最多只能被拿一次 完全背包：每个物品可被拿无限次数 举例，背包最大重量为4，物品为： 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 每件商品都有无限个！ 问背包能背的物品最大价值是多少？ 确定dp数组与下标含义 先使用较好理解的二维dp数组：dp[i][j]表示从下标为从0到i的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少 确定递推公式 以dp[1][4]为例，有两种情况，1）放物品1；2）不放物品1 如果装不下物品1，那背包的价值是dp[0][4]吗？即 只放物品0 并且容量为4的情况？如下图所示 没错，在装不下放物品1时的情况与01背包一致； 如果装得下物品1，那背包的价值上是max(dp[0][4], dp[0][4 - weight[1]] + val[4]) 吗？ 并不是！在“装得下物品1时”的情况与01背包不同 （如下图所示） 在01背包时，因为物品1只能被装一次，所以我们只会考虑dp ...

LeetCodeCampsDay36动态规划part04 01背包，分割等和子集的变式题目 416.分割等和子集是问：能否将背包装满到target值 1049.石头：尽量将背包装满到target值，如果装不到，则最小差值是多少 494.目标和：装满一个到target值，有多少种方法 474.一和零：装满一个背包，最多有多少物品 1049. 最后一块石头的重量 II https://leetcode.cn/problems/last-stone-weight-ii/ 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 示例 1： 1234567输入：stones = ...

LeetCodeCampsDay35动态规划part03 背包问题/01背包/一维dp数组与二维dp数组的执行区别 背包问题 背包问题可以分成01背包/完全背包/多重背包与分组背包； 不过搞定01背包与完全背包就可以了 01背包 有n件物品和一个最多能背重量为w 的背包。 第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。 这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？ 每一件物品其实只有两个状态，取或者不取 ，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。 所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！ 在下面的讲解中，我举一个例子： 背包最大重量为4。 物品为： 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 问背包能背的物品最大价值是多少？ ...