动态规划02-斐波那契类型二

1. 使用最小花费爬楼梯

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

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

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

真题点击此处：746.使用最小花费爬楼梯

解题方法：动态规划
思路：对于此题来说，假设cost的长度为n，那么我们可以令前n个楼梯的下标为0–n-1,因此这个问题本质上就是算出当下标为n时的费用即可。我们假设爬到当前下标 i 的耗费为dp[i]（不包括当前 i 位置的消费），由题意可知，每次可以爬一个或两个台阶，那么我们就可以得出以下的动态转移方程：dp[i]=min(dp[i?1]+cost[i?1],dp[i?2]+cost[i?2])。
依次计算 dp 中的每一项的值，最终得到的 dp[n]即为达到楼层顶部的最小花费。

以下为代码实现：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n+1)
        for i in range(2,n+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[n]

时间复杂度：O（n），使用了一次循环。
空间复杂度：O（n），使用了长度为n+1的数组。

上述代码的时间复杂度和空间复杂度都是 O(n)。注意到当 i≥2 时，dp[i]只和 dp[i?1] 与 dp[i?2]有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。
以下为代码实现：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n=len(cost)
        prev = curr = 0
        for i in range(2,n+1):
            nxt = min(curr + cost[i-1], prev + cost[i-2])
            prev, curr = curr, nxt
        return nxt

时间复杂度：O（n），同样的也是一次循环。
空间复杂度：O（1），只使用了常量级的额外空间。

我们也可以直接在cost[i]上修改值，但是这样的话就要加上当前位置的cost[i],并且在循环结束后需要再判断一次最后两个值的大小。
以下为代码实现：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n=len(cost)
        for i in range(2,n):
            cost[i] = cost[i] + min(cost[i-1], cost[i-2])
        
        return min(cost[-1], cost[-2])

时间复杂度：O（n），一次循环。
空间复杂度：O（1），是在原本的数组上更改，并未创建额外的数组。

2. 打家劫舍

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

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

真题点击此处：198.打家劫舍

解题方法：动态规划
思路：对于一间房屋，偷窃该房屋可以获得最高总金额。对于两间相邻的房屋，只能选择其中金额较高的一间进行偷窃，以获取最高总金额。对于超过两间房屋的情况，每间房屋都有两个选项：偷窃该房屋或者不偷窃该房屋。如果选择偷窃该房屋，需要加上前两间房屋中的最高总金额；如果选择不偷窃该房屋，就直接等于前一间房屋的最高总金额。最后选取偷窃和不偷窃中的最大值作为当前房屋的最高总金额，并重复这个过程直到最后一间房屋。

我们用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

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

以下为代码实现：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2,n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[n-1]

时间复杂度：O（n），使用了一次循环遍历所有房屋。
空间复杂度：O（n），使用了长度为n的一维数组存储dp的值。

由于对于每次需要计算的第i个房屋来说，它只与前面的两个值有关，因此我们可以优化空间复杂度为O（1）。
以下为代码实现：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        a, b = nums[0], max(nums[0],nums[1])
        for i in range(2, n):
            a, b = b, max(b, a + nums[i])

        return b

时间复杂度：O（n），仍然是使用了一次循环。
空间复杂度：O（1），只使用了额外的两个变量存储数据。

3. 删除并获得点数

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

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

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

真题点击此处：740.删除并获得点数

解题方法：动态规划
思路：根据题意，在选择了元素 x 后，所有等于 x-1 或 x+1 的元素会从数组中删除。如果数组中仍然有多个值为 x 的元素，由于所有等于 x-1 或 x+1 的元素已经被删除，我们可以直接删除 x 并获得其点数。因此，若选择了 x，则所有等于 x 的元素也应一同被选择，以最大化获得点数。我们可以用一个数组 sum 记录数组 nums 中所有相同元素之和，即 sum[x]=x*cx，其中 cx 表示元素 x 在数组中出现的次数。如果选择了 x，则可以获取 sum[x] 的点数，并且无法再选择 x-1 和 x+1。这样的话这题的解题思路就跟上题的打家劫舍是一样的了。
以下为代码实现：

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        maxnum = max(nums)
        cnt = [0] * (maxnum + 1)

        for num in nums:
            cnt[num] += num

        a, b = cnt[0], cnt[1]
        for i in range(2,len(cnt)):
            c = max(cnt[i]+a, b)
            a, b = b, c
        return b

时间复杂度：时间复杂度：O(N+M)，其中 N是数组 nums的长度，M 是 nums 中元素的最大值。
空间复杂度：O（M），使用了一个数组来存储cnt[num]的值。