Home

题目链接 这题和完全背包问题相似，不同处在于这题要求容积要恰好填满，但是完全背包问题只要求“不超过”，并且这题要求的是方案数，而完全背包问题要求一个小于容积的最大值。首先尝试用填满二维表格的方法，我们设f[i][j]为考虑前i种硬币，凑出金额为j的最少数目。考虑第i种硬币，我们可以不拿，或者拿i…k个，直到超出总金额。f[i][j] = min(f[i-1][j], f[i-1][j-c]+1, f[i-1][j-2c]+2, …, f[i-1][j-kc]+k)，又因为其中包含了大量冗余的运算，例如: f[i][j-c] = min(f[i-1][j], f[i-1][j-2c]+1, …, f[i-1][j-kc]+(k-1))，将两者合并可以得到f[i][j] = min(f[...

题目链接 这是一个区间dp的题目。我们先定义一个二维数组dp, dp[i][j]表示字符串s[i…j]的最长回文子序列的长度。假设对某个序列上的两个位置i，j，有另外的两个位置i+1和j-1。假设我们已经知道了dp[i+1][j-1]，我们如何计算dp[i][j]呢？我们只需要观察s[i]等不等于s[j]，当s[i]==s[j]时，那么就说明在原先的基础上又增加了回文子序列的长度，dp[i][j] = dp[i+1][j-1]+2，当s[i]!=s[j]时，那么说明s[j], s[j]中至少有一个不在回文子序列中，这时dp[i][j]只需取两者之间的最大值即可。即dp[i][j] = max(dp[i][j-1], dp[i+1][j])。由于每一个字符自身能构成一个回文子序列且长度...

题目链接 这题和完全背包问题相似，不同处在于这题要求容积要恰好填满，但是完全背包问题只要求“不超过”，并且这题要求的是方案数，而完全背包问题要求一个小于容积的最大值。首先尝试用填满二维表格的方法，我们设f[i][j]为考虑前i种硬币，凑出金额为j的最少数目。考虑第i种硬币，我们可以不拿，或者拿i…k个，直到超出总金额。f[i][j] = min(f[i-1][j], f[i-1][j-c]+1, f[i-1][j-2c]+2, …, f[i-1][j-kc]+k)，又因为其中包含了大量冗余的运算，例如: f[i][j-c] = min(f[i-1][j], f[i-1][j-2c]+1, …, f[i-1][j-kc]+(k-1))，将两者合并可以得到f[i][j] = min(f[...

题目链接 一个动态规划的题目，可以联想成完全背包问题。这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。 python: class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: size = len(s) dp = [False]*(size+1) dp[0] = True for i in range(size): for j in range(i+1, size+1): if dp[i] and s[i:j] in wordDict: ...

题目链接 一个动态规划的题目，可以联想成完全背包问题。这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。 python: class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: size = len(s) dp = [False]*(size+1) dp[0] = True for i in range(size): for j in range(i+1, size+1): if dp[i] and s[i:j] in wordDict: ...

题目链接 一个二维的dp，很熟练了。这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。 python: class Solution: def minPathSum(self, grid: List[List[int]]): lrow, lcol = len(grid), len(grid[0]) for i in range(1, lrow): grid[i][0] += grid[i-1][0] for j in range(1, lcol): grid[0][j] += grid[0][j-1] print(grid) ...

题目链接 继续回溯法，有个小技巧就是用if helper(): return True 而非直接使用return helper()，否则会因为虽然一开始进入了helper函数而后续的要求没满足导致直接返回结果，实际上还有其他符合helper函数的条件要在比较完后续的之后才能下结论，不这样处理就错了。算法的时间复杂度有个宽松的上界是O（MN3**L），M和N分别是矩阵的长宽，L是word的长度，由于剪枝的存在所以时间复杂度不会这么大。空间复杂度是O（NM），我们额外开辟了visited数组。 python: class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ...

题目链接 回溯算法，写了一下就写出来了，还行。时间复杂度与第N个卡特兰数有关，空间复杂度是O（N）。 python: class Solution: def generateParenthesis1(self, n: int) -> List[str]: d = { "(": 1, ")": -1 } def recursion(path, value): if len(path) == 2*n: if value == 0: res.append("".join(path)...

题目链接 一个二维的dp，很熟练了。这个算法的时间复杂度是O（NM），空间复杂度是O（NM）。 python: class Solution: def minPathSum(self, grid: List[List[int]]): lrow, lcol = len(grid), len(grid[0]) for i in range(1, lrow): grid[i][0] += grid[i-1][0] for j in range(1, lcol): grid[0][j] += grid[0][j-1] print(grid) ...

题目链接 回溯算法，写了一下就写出来了，还行。时间复杂度与第N个卡特兰数有关，空间复杂度是O（N）。 python: class Solution: def generateParenthesis1(self, n: int) -> List[str]: d = { "(": 1, ")": -1 } def recursion(path, value): if len(path) == 2*n: if value == 0: res.append("".join(path)...