algorithm-problem-leetcode-2585
2585. 获得分数的方法数(1910)
考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。
注意，同类型题目无法区分。
比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。
示例 1：
12345678910输入：target = 6, types = [[6,1],[3,2],[2,3]]输出：7解释：要获得 6 分，你可以选择以下七种方法之一：- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的 ...
algorithm-problem-leetcode-1155
1155. 掷骰子等于目标和的方法数(1654)
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 k^n 种方式），使得骰子面朝上的数字总和等于 target。
由于答案可能很大，你需要对 10^9 + 7 取模。
示例 1：
1234输入：n = 1, k = 6, target = 3输出：1解释：你掷了一个有 6 个面的骰子。得到总和为 3 的结果的方式只有一种。
示例 2：
1234输入：n = 2, k = 6, target = 7输出：6解释：你掷了两个骰子，每个骰子有 6 个面。有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。
示例 3：
123输入：n = 30, k = 30, target = 500输出：222616187解释：返回的结果必须对 109 + 7 取模。
提示：
1 <= n, k <= 30
1 <= target <= 1000
思路：多重背包（背包恰好装 ...
algorithm-problem-leetcode-322
322. 零钱兑换
给你一个整数数组 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] <= 2^31 - 1
0 <= amount <= 10^4
思路：背包恰好装capacity，其中每个物品价值为1，求最小价值和
物品重量 = 硬币面额
物品价值 = 1
背包容量 = 需要的总金额
1234567891011121314151617181920class Solution { public ...
algorithm-problem-leetcode-518
518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
1234567输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1
示例 2：
123输入：amount = 3, coins = [2]输出：0解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
12输入：amount = 10, coins = [10] 输出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
思路：背包恰好装capacity，求方案数
1234567891011121314151617c ...
algorithm-problem-leetcode-3180
3180. 执行操作可获得的最大总奖励 I（1849）
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1：
**输入：**rewardValues = [1,1,3,3]
**输出：**4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
示例 2：
**输入：**rewardValues = [1,6,4,3,2]
**输出：**11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
提示：
1 <= rewardValues.length <= 2000
1 <= rewardValues[ ...
algorithm-problem-leetcode-494
494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
12345678输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3
示例 2：
12输入：nums = [1], target = 1输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= ...
algorithm-problem-leetcode-1449
1449. 数位成本和为目标值的最大数字
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 “0” 。
示例 1：
12345678910111213输入：cost = [4,3,2,5,6,7,2,5,5], target = 9输出："7772"解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。 数字 成本 1 -> 4 2 -> 3 3 -> 2 4 -> 5 5 ...
algorithm-problem-leetcode-689
689. 三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
示例 1：
1234输入：nums = [1,2,1,2,6,7,5,1], k = 2输出：[0,3,5]解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
示例 2：
12输入：nums = [1,2,1,2,1,2,1,2,1], k = 2输出：[0,2,4]
提示：
1 <= nums.length <= 2 * 10^4
1 <= nums[i] < 2^16
1 <= k <= floor(nums.length / 3)
123456789101112131415161718192021222324class ...
algorithm-problem-leetcode-300
300. 最长递增子序列
给你一个整数数组 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
-10^4 <= nums[i] <= 10^4
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
动态规划，线性dp
123456789101112131415class Solution { public int lengthOfLIS(int[] nums) { // f[i]: 考 ...
algorithm-problem-leetcode-1143
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
123输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
123输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
123输入：text ...