leecode刷题笔记（四）

2020-06-27

根据不同的解答方法，总结leecode不同题型。

方法四：动态规划

动态规划题目的四个基本步骤：

定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序
空间优化（可选）

线性动态规划

198. 打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

解答：

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

        for i in nums[2:]:
            a1,a2 = a2,max(i+a1,a2)
        return a2

740. 删除与获得点数

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

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

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

示例 1:

输入: nums = [3, 4, 2]
输出: 6
解释: 
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。

解答：

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        prev = None
        avoid = using = 0
        for k in sorted(count):
            if k - 1 != prev:
                avoid, using = max(avoid, using), k * count[k] + max(avoid, using)
            else:
                avoid, using = max(avoid, using), k * count[k] + avoid
            prev = k
        return max(avoid, using)

二维动态规划

583. 两个字符串的删除操作

给定两个单词 word1 和 word2*，找到使得 *word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

1
2
3

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

解答：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        m = len(word1)
        n = len(word2)
        d = [[0 for i in range(n+1)]for j in range(m+1)]
        if m==0 and n==0:
            return 0
        if m==0:
            return n
        if n==0:
            return m
        for i in range(m+1):
            for j in range(n+1):
                if i==0 or j==0:
                    continue
                if word1[i-1]==word2[j-1]:
                    d[i][j] =d[i-1][j-1]+1
                else:
                    d[i][j] =max(d[i][j-1],d[i-1][j])
        return m+n-2*d[m][n]

背包问题

背包问题是经典的动态规划问题，它一共有 9 个分类，建议耐心阅读，理解之后你的动态规划水平一定会有一个质的飞跃。

先来浏览一下这 9 个问题的名称：

01 背包问题
完全背包问题
多重背包问题
混合背包问题
二维费用背包问题
分组背包问题
背包问题求方案数
求背包问题的方案
有依赖的背包问题

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

1
2
3

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

解答：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for i in range(1,amount+1):
            for j in coins:
                if i-j>=0:
                    dp[i]=min(dp[i],dp[i-j]+1)
        
        if dp[amount]==float('inf'):
            return -1
        else:
            return dp[amount]

总结：完全背包问题求最小值

面试题 08.11. 硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

class Solution:
    def waysToChange(self, n: int) -> int:
        if n<5:
            return 1
        if 5<=n<10:
            return 2
        if 10<=n<25:
            c = 3
        if n>=25:
            c = 4
        
        
        a = [[1 for i in range(n+1)]for j in range(c)]
        b = [1,5,10,25]
        for i in range(1,c):
            for j in range(1,n+1):
                if j-b[i]>=0:
                    a[i][j]=a[i-1][j]+a[i][j-b[i]]
                else:
                    a[i][j]=a[i-1][j]
        return a[c-1][n]%1000000007

总结：完全背包问题求方案数。