OJ刷题总结6——从记忆化搜索到递推

198

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

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

对于某一个i，要么拿，要么不拿

  • 拿：dp[i] = dp[i - 2] + nums[i]
  • 不拿：dp[i] = dp[i - 1]

dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])

1
2
3
4
5
6
7
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 2)
        for i, x in enumerate(nums):
            dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
        return dp[-1]

空间优化：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # dp = [0] * (n + 2)
        dp0 = 0
        dp1 = 0
        for i, x in enumerate(nums):
            new_dp = max(dp1, dp0 + nums[i])
            dp0 = dp1
            dp1 = new_dp
        return new_dp

70

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

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

对于某一个i，可以从i - 1或者i - 2到达

即dp[i] = dp[i - 1] + dp[i - 2]

1
2
3
4
5
6
7
8
class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

746

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

dp[i]: 到达当前i，最少要花dp[i]

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

1
2
3
4
5
6
7
8
9
10
def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    dp0 = 0
    dp1 = 0
    for i in range(2, n + 1):
        new_dp = min(dp1 + cost[i - 1], dp0 + cost[i - 2])
        dp0 = dp1
        dp1 = new_dp
    return dp1

377

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

对于nums中的某一个数x, if i >= x(i 为 dp下标)，dp[i] += dp[i - x]

dp[0] = 1，这是因为只有当什么都不拿的时候，才能为0，所以只有1种方案

1
2
3
4
5
6
7
8
9
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1   # 只有当什么都不拿的时候，才能为0，所以只有1种方案
        for i in range(target + 1):
            for _, x in enumerate(nums):
                if (i >= x):
                    dp[i] += dp[i - x]
        return dp[-1]

2466

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

  • 将 '0' 在字符串末尾添加 zero 次。
  • 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

dp[i]: 长度为i时，有几种字符串

  • 字符串后面加’0’: dp[i] = dp[i - zero]

  • 字符串后面加’1’: dp[i] = dp[i - one]

dp[i] = dp[i - zero] + dp[i - one]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    '''
    dp[i]: 长度为i时，有几种字符串

    dp[i] = dp[i - zero] + dp[i - one]
    '''
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        dp = [0] * (high + 1)
        dp[0] = 1
        
        MOD = 10**9 + 7

        for i in range(1, high + 1):
            if i >= zero:
                dp[i] += dp[i - zero] % MOD
            if i >= one:
                dp[i] += dp[i - one] % MOD
        return sum(dp[low:]) % MOD

740

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

变相的打家劫舍。只是这里的“舍”，是指nums中的隔壁

我们先预处理一下，将题目的nums转化成舍：

1
2
3
4
mx = max(nums)
fam = [0] * (mx + 1)
for _, x in enumerate(nums):
    fam[x] += x

然后，打家劫舍

1
2
3
4
5
6
def rob(self, fam):
    n = len(fam)
    dp = [0] * (n + 2)
    for i in range(n):
        dp[i + 2] = max(dp[i + 1], dp[i] + fam[i])
    return dp[-1]

2320

一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

对于第i块，dp[i] = dp[i - 1] + dp[i - 2]

1
2
3
4
5
6
7
8
9
class Solution:
    def countHousePlacements(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 2
        MOD = int(10 ** 9 + 7)
        for i in range(2, n + 1):
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        return (dp[-1] * dp[-1]) % MOD

213

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

对于第0个房屋：

  • 盗了：计算下标0 到 n-2的max金额
  • 否则：计算下标1 到 n-1的max金额

执行两遍打家劫舍rob

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def onerob(self, nums):
        n = len(nums)
        dp = [0] * (n + 2)
        for i in range(n):
            dp[i + 2] = max(dp[i + 1], dp[i] + nums[i])
        return dp[-1]

    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        return max(self.onerob(nums[:-1]), self.onerob(nums[1:]))

LCR 166

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

  • 只能从架子的左上角开始拿珠宝
  • 每次可以移动到右侧或下侧的相邻位置
  • 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

二维的dp

f[i][j]: 返回走到[i][j]时，拿到了最大的珠宝

f[i][j] = max(f[i - 1][j], f[i][j - 1]) + frame[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    '''
    f[i][j]: 返回走到[i][j]时，拿到了最大的珠宝
    f[i][j] = max(f[i - 1][j], f[i][j - 1]) + frame[i][j]
    '''
    def jewelleryValue(self, frame: List[List[int]]) -> int:
        row = len(frame)
        col = len(frame[0])
        f = [[0] * (col + 2) for _ in range(row + 2)]
        for i in range(row):
            for j in range(col):
                f[i + 2][j + 2] = max(f[i + 1][j + 2], f[i + 2][j + 1]) + frame[i][j]
        return f[row + 1][col + 1]