1 动态规划问题

必考题

解题思路：状态定义，转移方程，初始条件，返回值

1.1 解题思路

一言以蔽之：大事化小，小事化了。　　

将一个大问题转化成几个小问题；　　求解小问题；　　推出大问题的解。总结为下面三点

状态
选择
穷举

综上其实动态规划大可分为如下几类问题常见关键词：求。。方法数，集合数，路径数，返回。。长度，最少，最多，最大，最小，最长，最短。。。 解题思路才是最关键的，而不是刷了多少题 今天看到一个问题，其实大部分问题都可以归为完全背包问题或者0|1背包问题，寻找到子问题是关键。

1.2 最大子序和问题

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释:连续子数组[4,-1,2,1] 的和最大，为6。

dp[i]和dp[i-1]差一个nums[i]

找出状态转移方程：\(d p[i]=\max \{n u m s[i], d p[i-1]+n u m s[i]\}\)

这一种写法比较直观


from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)] # 状态（明确dp表示包含第i个元素的最大和）

        dp[0] = nums[0]
        for i in range(1, size): # 选择
            dp[i] = max(dp[i - 1] + nums[i], nums[i]) # 穷举 
        return max(dp)

1.3 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路：枚举

给个时间复杂度为\(O(n^2)\)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums==[]: return 0
        length=len(nums)
        # 暂存子序列长度，1 个字符显然是长度为 1 的上升子序列
        dp=[1 for _ in range(length)]# 状态：dp[i] 表示以 nums[i] 结尾的「上升子序列」的长度
        for i in range(length):
            for j in range(0,i):选择
                if nums[i]>nums[j]:# 当nums[i]前面存在小于nums[i]的nums[j],
                    dp[i]=max(dp[i],dp[j]+1)# 穷举：当nums[i]前面存在小于nums[i]的nums[j],
        return max(dp)

1.4 最长公共子序列长度

问题描述：

给定两个字符串A和B，返回两个字符串的最长公共子序列，并记录最长公共子序列的长度。例如，两个字符串A、B分别为“1A2C3D4B56”和“B1D23CA45B6A”，则“123456”和“12C4B6”都是最长公共子序列，且最长公共子序列长度为6。（最长公共子序列可能不唯一，但长度唯一。）

maxl_mat[i][j]表示解之到A的第i个字符和截止到B的第j个字符初始化一个二维数组：初始化一个二维数组，行数为A的大小，列数为B的大小

难点在于想明白两种情况。

np.zero()好用的

看下道题，同类型的题目，没意思。。

1.5 最长重复子数组长度

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。

1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100

和最长公共子序列长度的题类似，这类都是二维数组

# 动态规划
class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        #dp[i][j] = longest(A[:i],B[:j])
        res = -float('inf')
        dp = [[0 for j in range(len(B)+1)] for i in range(len(A)+1)]
        for i in range(1,len(A)+1):
            for j in range(1,len(B)+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0
                res = max(dp[i][j],res)
        return res

1.6 最短路径和问题

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入: [ [1,3,1], [1,5,1], [4,2,1]] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

最短路径和的问题二维的动态规划

i横向,j纵向

class Solution:
    def minPathSum(self, grid: [[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0: continue
                elif i == 0:  grid[i][j] = grid[i][j - 1] + grid[i][j]
                elif j == 0:  grid[i][j] = grid[i - 1][j] + grid[i][j]
                else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[-1][-1]

1.7 爬楼梯问题

斐波那契数列：只需要考虑最后到达最后一阶实现的几种情况

题目一般有2种，可以爬2阶或者3阶，思路一样，递归+DP，但是要注意时间复杂度。。

或者爬1阶，2阶

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

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

注意：给定 n 是一个正整数。

示例 1：

输入： 2 输出： 2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：

输入： 3 输出： 3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

class Solution:
    def climbStairs(self, n: int) -> int:
        res = [0] * 46
        res[0] = 1
        res[1] = 2
        
        for i in range(2,n):
            res[i] = res[i-1] + res[i-2]
        return res[n-1]

画个图发现就是二叉树的遍历

1.8 母牛生产一

#File Name : 母牛问题.py
# 开始有一只母牛 母牛每年可以生一只母牛
# 新出生三年后才能每年生一只母牛  假设都不会死
# 第n年有几只

def cowNum(N):
    if N<=1:
        return 1
    return cowNum(N-1)+cowNum(N-3)
 
a = cowNum(7)
print(a)
 
# f(n) = f(n-1) + f(n-3)
# 今年的牛 = 去年的牛 + 三年前牛的数量
# 因为三年前的牛现在每个牛都可以生一只牛

1.9 母牛生产二

母牛从3-7岁初每年会生产1头小母牛，10岁后死亡（10岁仍然存活），假设初始有1头刚出生的母牛，请问第n年有多少头母牛？（年从第一年开始计数）

可以列个表格找找规律

写个1-12岁就查差不多了边界条件比较多参考：博客园

（1）sum：记录每次的求和部分

（2）opt[ i ]：记录第 i 年母牛的个数， opt[ -1] ：表示最终的输出结果

（3）一次循环遍历，记录 sum 和 opt[ i ]，时间复杂度：O(n)

# 母牛生产
import sys
for line in sys.stdin:
    n = int(line)
    if n < 3:
        print('1')
    else:
        opt = [0 for i in range(n + 1)]
        opt[0] = -1
        opt[1] = 1
        opt[2] = 1

        sum = 0
        for i in range(3, n+1):
            if i >=  3 and i <=7:
                sum = sum + opt[i - 2]
                opt[i] = sum + 1

            elif i >= 8 and i <= 10:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum + 1

            else:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum

        print(opt[-1])

1.10 不同路径

解题思路:与爬楼梯的思路一致

令 dp[i][j] 是到达 i, j 最多路径

状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

时间复杂度：O(m*n)

空间复杂度：O(m∗n)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        d = [[0]*n for _ in range(m)]
        for i in range(m):
            d[i][0] = 1 # 从（0,0）出发，边界上的点只能一直向右走或者向下走，所以到边界上的点只有一种走法
        for j in range(n):
            d[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                d[i][j] = d[i-1][j]+d[i][j-1]
        return d[-1][-1]

优化：因为我们每次只需要 dp[i-1][j],dp[i][j-1]

因此可以考虑降空间复杂度，减少一个数组

当前点为上面点加左边点，那么计算第二行时可以直接在第一行计算，及当前点加左边点就ok了，当前点原来值表示上一行的上面点的值。所以实际一行数组重复计算就完事了。

这个思路太强了，不好想~

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        cur = [1] * n 
        for i in range(1, m):
            for j in range(1, n):
                cur[j] += cur[j-1] #等号右边分别是该位置上边的值和左边的值
        return cur[-1]

1.11 最长回文字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。示例 2：

输入: “cbbd” 输出: “bb”

动态规划法

学习weiwei思路，很快就理解了，这里写下我的总结

动态规划：填dp表、当前ij状态、过去ij状态、如何联合得到输出、边界条件

定义状态：题目让我们求什么，就把什么设置为状态题目求s中最长的回文子串，那就判断所有子串是否为回文子串，选出最长的因此：dp[i][j]表示s[i:j+1]是否为回文子串（这里+1是为了构造闭区间）

状态转移方程：对空间进行分类讨论（当前ij状态、过去ij状态如何联合得到输出）当前ij状态：头尾必须相等（s[i]==s[j]）过去ij状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）边界条件：只要是找过去ij状态的时候，就会涉及边界条件（即超出边界情况处理）当i==j时一定是回文 j-1-(i+1)<=0,即j-i<=2时，只要当s[i]==s[j]时就是回文，不用判断dp[i+1][j-1] dp[i][j] 为截取的子串

初始状态：这里已经直接判断j-i<=2的情况了，因此用不到初始状态，可以不设

输出内容：每次发现新回文都比较一下长度，记录i与长度

优化空间提速

参考：_Breiman


class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        size = len(s)
        # 特殊处理
        if size == 1:
            return s
        # 创建动态规划dynamic programing表
        dp = [[False for _ in range(size)] for _ in range(size)]
        # 初始长度为1，这样万一不存在回文，就返回第一个值（初始条件设置的时候一定要考虑输出）
        max_len = 1
        start = 0
        for j in range(1,size):
            for i in range(j):
                # 边界条件：
                # 只要头尾相等（s[i]==s[j]）就能返回True
                if j-i<=2:
                    if s[i]==s[j]:
                        dp[i][j] = True
                        cur_len = j-i+1
                # 状态转移方程 
                # 当前dp[i][j]状态：头尾相等（s[i]==s[j]）
                # 过去dp[i][j]状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）
                else:
                    if s[i]==s[j] and dp[i+1][j-1]:
                        dp[i][j] = True
                        cur_len = j-i+1
                # 出现回文更新输出
                if dp[i][j]:
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i

        return s[start:start+max_len]

双指真法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n):
                j = i + l
                if j >= len(s):
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

1.12 回文子字符串数量

题目链接：https://leetcode-cn.com/problems/palindromic-substrings/

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：“aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

输入的字符串长度不会超过 1000 。

动规五部曲：

1.确定dp数组（dp table）以及下标的含义布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2.确定递推公式在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串情况二：下标i 与 j相差为1，例如aa，也是回文子串情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1): #注意遍历顺序，这个真的额是重点
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1: #情况一 和 情况二
                        result += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]: #情况三
                        result += 1
                        dp[i][j] = True
        return result

1.13 最大乘积和

这个题一开始我想的很简单，就类似与最大上升子序和来做了，结果。。。==

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例 2:

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况：

如果该元素为正数：

如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大
如果到上一个元素为止的最大乘积是负数，那么最大乘积就会变成该元素本身，且连续性被断掉

如果该元素为负数：

如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大
如果到上一个元素为止的最大乘积是正数，那么最大乘积就会不变，且连续性被断掉

以上四种情况中说到的最大乘积都是临时最大乘积，每遍历新的元素都需要进行比较来确定真正的最大乘积。

如果细心的话就可以发现，如果要得到乘以当前元素以后的最大乘积，需要记录最大乘积，也要记录最小乘积，因为最小值可能翻身变最大值。

对对对对。。。需要用两个记录两个值。。

负负为正负正为负

但是看成是动态规划问题挺不好想的，只能多看几遍了

时间复杂度是O(n)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums: return 
        res = nums[0]
        pre_max = nums[0]
        pre_min = nums[0]
        for num in nums[1:]:
            cur_max = max(pre_max * num, pre_min * num, num)#pre_max:之前的最大值
            cur_min = min(pre_max * num, pre_min * num, num)#pre_min:之前的最小值，num:当前值
            res = max(res, cur_max)
            pre_max = cur_max
            pre_min = cur_min
        return res

1.14 买卖股票专题

买卖股票的最佳时机 I

交易限制在一次了

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

分析：第一题，相对简单，只能有一次交易。刚看到第一反应可能是遍历两次，找出所有的利润，选个最大的，意料之中，复杂度O（n^2）肯定超时。在一次遍历中，可以记录最小值，同时记录对应的利润即可。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)<2:
            return 0
        profit = 0 #最初的利润是0
        minprice = prices[0]
        for i in prices:
            minprice = min(i,minprice)
            profit = max(i-minprice,profit) #找到最小的价格和最大的价格做差，与当前利润进行比较
        return profit

动态规划实现

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if not n or n < 2:
            return 0
        dp = [[0,0] for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]

        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1] = max(dp[i-1][1],-prices[i])
        return dp[n-1][0]

买卖股票的最佳时机 II

无限次交易

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。示例 2:

输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

分析：不限制交易次数，其实看起来比还要简单，可以直接一次遍历，把后一项大于前一项时，两者差值相加即可。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        temp = prices[0]
        profit = 0
        for i in prices:
            if i > temp:
                profit = profit + i - temp
            temp = i
        return profit

买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

分析：此题加深了难度，限制了建议次数不大于2。最开始的想法是二分，遍历所有值作为二分点，分成左右两部分，分别求利润再求和，最后取最大，时间复杂度O(N^2)，结果在倒数第二个评测时超时。优化一下，可以先从前往后遍历，按照 I中的思路，将遍历到的每个值对应的最大利润存在一个列表中，然后从后往前遍历，在求此时的最大利润时，同时加上数组中的对应值，再取最大，即为所求。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)<2:
            return 0
        minprice = prices[0]
        maxprice = prices[len(prices)-1]
        profit1 = 0
        profit2 = 0
        profit = 0
        a = []
        for m in range(0,len(prices)):
            profit1 = max(profit1,prices[m]-minprice)
            minprice = min(prices[m],minprice)
            a.append(profit1)
        for n in range(len(prices)-2,-1,-1):
            maxprice = max(prices[n],maxprice)
            profit2 = max(profit2,maxprice-prices[n])
            profit = max(profit,a[n]+profit2)
        return profit

1.15 完全平方数

这题没想起来怎么转，知道想起找零钱的那个题。

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2:

输入: n = 13 输出: 2 解释: 13 = 4 + 9.

感觉有点像coin那个题

dp[i]表示i最少可以由几个平方数构成。

初试化\(dp=[0,1,2,⋯,n]\)，长度为n+1，最多次数就是全由1构成。

遍历dp，对于i，遍历区间[2,n+1)：

遍历所有平方数小于i的数j，遍历区间\([1,int(\sqrt{i})+1)\)： \(dp[i]=min(dp[i],dp[i-j*j]+1)\)。始终保存所有可能情况中的最小值。返回dp[n]

因此时间复杂度是：O(n) 空间复杂度：O(n)

class Solution:
    def numSquares(self, n: int) -> int:
        dp=[i for i in range(n+1)]
        for i in range(2,n+1):
            for j in range(1,int(i**(0.5))+1):
                dp[i]=min(dp[i],dp[i-j*j]+1)
        return dp[-1]

1.16 找零钱问题

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

示例 1:

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

输入: coins = [2], amount = 3 输出: -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 coin in coins:
                if i>=coin:
                    dp[i]=min(dp[i],dp[i-coin]+1)
        return dp[-1] if(dp[-1]!=float('inf')) else -1

目前的时间复杂度O(amount*len(coins))

有么有更快的方法？有的，回溯算法+dbf

可以查查，理解下~ 找零钱问题是背包问题的一个例子

1.17 单词切分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词。示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

解题思路

初始化 \(d p=[\text { False, } \cdots, \text { False], 长度为 } n+1 . n \text { 为字符串长度。 } d p[i] \text { 表示 } s \text { 的前 } i\) 位是否可以用 wordDict 中的单词表示。
初始化 \(d p[0]=T r u e,\) 空字符可以被表示
遍历字符串的所有子串，遍历开始索引 \(i,\) 遍历区间 \([0, n)\) 。遍历结束索引 \(j,\) 遍历区间 \([i+1, n+1)\)

若 \(d p[i]=\) True 且 \(s[i, \cdots, j)\) 在 wordlist 中: \(d p[j]=T r u e_{\circ}\) 解释: \(d p[i]=\) True i兄明 \(s\) 的前 \(i\) 位可以用 \(w o r d D i c t\) 表示, 则 \(s[i, \cdots, j)\) 出现在 \(w o r d D i c t\) 中，说明 \(s\) 的前 \(j\) 位可以表示。

返回 \(d p[n]\)

问题不难，就是没想到用动态规划

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:       
        n=len(s)
        dp=[False]*(n+1)
        dp[0]=True
        for i in range(n):
            for j in range(i+1,n+1):
                if(dp[i] and (s[i:j] in wordDict)):
                    dp[j]=True
        return dp[-1]

1.18 打家劫舍专题

1.18.1 打家劫舍一

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

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

示例 1:

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

class Solution:
    def rob(self, nums: List[int]) -> int:
       prev = 0
       curr = 0
    
     # 每次循环，计算“偷到当前房子为止的最大金额”
       for i in nums:
        # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
           prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]

       return curr

或者另一种写法,即动态规划，


class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums)==1:
            return nums[0]
        sumList = [nums[0]]      #存放盗窃的每一个房间的最大收益
        sumList.append(max(nums[0], nums[1]))
        for i in range(2,len(nums)):
            sumList.append(max(sumList[i-2]+nums[i], sumList[i-1]))
        return sumList[-1]

1.18.2 打家劫舍二之环形房屋

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

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

示例 1:

输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2:

输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

解题思路：可以开辟2个队列保存结果嘛,第一个队列保存从[0,n-1]的结果，第二个队列保存从[1,n]的结果

class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        if n<=2:
            return max(nums)
        dp1 = [0 for _ in range(n)]
        dp2 = [0 for _ in range(n)]
        # 初始化两个dp数组，dp1是计算的是[1,end],dp2计算的是[0,end-1],这个比较好想
        dp1[0] = 0
        dp1[1] = nums[1]
        dp2[0] = nums[0]
        dp2[1] = max(nums[0],nums[1])
        # 按照【打家劫舍 I】的转移方式执行两遍
        for i in range(2,n):
            dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i])
        for i in range(2,n-1):
            dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i])
        return max(dp1[-1],dp2[-2])

1.18.3 打家劫舍三之二叉树房屋

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

哎，这个小偷太能想了==

这道题采用的是后序遍历，由于还是不能打劫连着的房子，也就是说，父节点和子节点不能同时打劫，于是就产生两种情况：

打劫父节点，放弃打劫左右子节点
不打劫父节点，打劫左右子节点

确定递归函数的参数和返回值：我们这里应该是对某个节点而言的，可以打劫，也可不打劫，自然有两种状态，返回值就应该是这两个结果，这里用dp数组来表示，且长度为2，不妨设dp[0]表示不偷该节点所获得的最大金额，dp[1]表示偷该节点所获得的最大金额。确定终止条件：遇到空节点就返回，返回的应该是[0, 0]，很明显，房子都没有，那偷与不偷都是一毛钱都没有。确定遍历顺序：前面说了，应该采用后序：通过递归左节点，得到左节点偷与不偷获得的钱通过递归右节点，得到右节点偷与不偷获得的钱 4.单层递归的逻辑：

偷当前节点，则左右子节点不能偷，此时能获得的价值val1为当前节点的钱加上左右子节点不偷获得的钱不偷当前节点，则左右节点可考虑偷，将左右节点偷与不偷能获得的最大值的和作为当前节点的获得价值val2 此节点的dp = [val2, val1] 参考

这个解释好理解些

1.19 编辑距离

给你两个单词word1 和word2，请你计算出将word1转换成word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

示例1：

输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’) 示例2：

输入：word1 = “intention”, word2 = “execution” 输出：5 解释： intention -> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

解题思路：


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] # 状态
        for i in range(len(word1)+1): #选择
            dp[i][0] = i # word2不存在的时候
        for j in range(len(word2)+1):#选择
            dp[0][j] = j #word1不存在的时候
        for i in range(1, len(word1)+1):#选择
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]: #两个词的长度一样的时候
                    dp[i][j] = dp[i-1][j-1] 
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]

1.20 鸡蛋掉落

背包问题

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 f 确切的值的最小操作次数是多少？

示例 1：

输入：k = 1, n = 2 输出：2 解释：鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。如果它没碎，那么肯定能得出 f = 2 。因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。示例 2：

输入：k = 2, n = 6 输出：3 示例 3：

输入：k = 3, n = 14 输出：4

比较难的一个题，可以看下这里的思路

可以这样考虑。题目限定了 \(\mathrm{n}\) 层楼， \(k\) 个鸡蛋。如果我们尝试在 \(1 \sim n\) 层中的任意一层 \(x\) 扔鸡蛋: 1. 如果鸡蛋没碎，则说明 \(1 \sim \mathrm{x}\) 层都不用再考虑了，我们需要用 \(k\) 个鸡蛋去考虑剩下的 \(n-\) \(\mathrm{x}\) 层, 问题就从 \((n, k)\) 转变为了 \((\mathrm{n}-\mathrm{x}, \mathrm{k})\) 。 2. 如果鸡蛋碎了，则说明 \(x+1 \sim n\) 层都不用再考虑了，我们需要去剩下的 \(k-1\) 个鸡蛋考虑剩下的 \(x-1\) 层，问题就从 \((n, k)\) 转变为了 \((x-1, k-1)\) 。这样一来，我们就可以根据上述关系使用动态规划方法来解决这道题目了。具体步骤如下: 1. 划分阶段按照楼层数量、剩余鸡蛋个数进行阶段划分。 2. 定义状态定义状态 \(d p[i][j]\) 表示为：一共有 \(i\) 层楼， \(j\) 个鸡蛋的条件下，为了找出 \(f\) ，最坏情况下的最少扔鸡蛋次数。 3. 状态转移方程根据之前的描述， \(d p[i][j]\) 有两个来源，其状态转移方程为: \(d p[i][j]=\min _{1 \leq x \leq n}(\max (d p[i-x][j], d p[x-1][j-1]))+1\) 4. 初始条件给定鸡蛋 \(\mathrm{k}\) 的取值范围为 \([1,100], \mathrm{f}\) 值取值范围为 \([0, \mathrm{n}]\) ，初始化时，可以考虑将所有值设置为当前拥有的楼层数。 - 当鸡蛋数为 1 时， \(\operatorname{dp}[\mathrm{i}][1]=i\) 。这是如果唯一的蛋碎了，则无法测试了。只能从低到高，一步步进行测试，最终最少测试数为当前拥有的楼层数 (如果刚开始初始化时已经将所有值设置为当前拥有的楼层数，其实这一步可省略）。 - 当楼层为 1 时，在 1 层扔鸡蛋， \(d p[1][j]=1\) 。这是因为: ○ 如果在 1 层扔鸡蛋碎了，则 \(\mathrm{f}<1\) 。同时因为 \(\mathrm{f}\) 的取值范围为 \([0, \mathrm{n}]\) 。所以能确定 \(f=0\) 。 ○如果在 1 层扔鸡蛋没碎，则 \(f>=1\) 。同时因为 \(\mathrm{f}\) 的取值范围为 \([0, n]\) 。所以能确定 \(\mathrm{f}=0\) 。 5. 最终结果根据我们之前定义的状态， \(\operatorname{dp}[\mathrm{i}][j]\) 表示为：一共有 \(i\) 层楼， \(j\) 个鸡蛋的条件下，为了找出 \(\mathrm{f}\) ，最坏情况下的最少扔鸡蛋次数。则最终结果为 \(\mathrm{dp}[\mathrm{n}][\mathrm{k}]\) 。

以上就是常规思路

但是还有一种思路

\(d p[k][m]\) 的含义是 \(\mathrm{k}\) 个鸡蛋移动m 次最多能够确定多少楼层当在任一楼层仍下鸡蛋的时候，鸡蛋出现要么碎了，要么没碎这两种情况。碎了的话就测上面的楼层，上面的楼层数为: \(\mathrm{dp}[\mathrm{k}-1][\mathrm{m}-1]\) ，没碎就测下面的楼层，下面的楼层数为: \(\mathrm{dp}[\mathrm{k}][\mathrm{m}-1]\) ，最后加上扔下鸡蛋的这一楼层。所以总的楼层数 \(\mathrm{n}=\mathrm{dp}[\mathrm{k}-1][\mathrm{m}-1]+\mathrm{dp}[\mathrm{k}][\mathrm{m}-1]+1\) 递推公式是: \[ d p[k][m]=d p[k-1][m-1]+d p[k][m-1]+1 \] 时间复杂度: \(O(k n)\) ，有两个嵌套循环，空间复杂度: \(O(k n)\). 参考：jensen-huang

class Solution:
    def superEggDrop(self, k, n):

       # dp(k, n)表示楼层的高度
       dp = [[0]*(k+1) for _ in range(n+1)]
       m = 0
       while dp[m][k] < n:
           m += 1
           for i in range(1, k+1):
               dp[m][i] = dp[m-1][i-1] + 1 + dp[m-1][i]
       return m

6行代码：wyzJack267

class Solution(object):
    def superEggDrop(self, K, N): 
        f = [[0] * (K + 1) for _ in range(N + 1)]
        for i in range(1, N + 1): 
            for j in range(1, K + 1):
                f[i][j] = f[i - 1][j - 1] + 1 + f[i - 1][j]
                if f[i][K] >= N:
                    return i

1.21 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。

这道题拿到很容易去想拆成3个还是4个，以下题解参考代码随想录

动规五部曲，分析如下：

确定dp数组（dp table）以及下标的含义 dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

dp[i]的定义讲贯彻整个解题过程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

确定递推公式可以想 dp[i]最大乘积是怎么得到的呢？

其实可以从1遍历j，然后有两种渠道得到dp[i].

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

那有同学问了，j怎么就不拆分呢？

j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了。

那么从1遍历j，比较(i - j) * j和dp[i - j] * j 取最大的。

递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp的初始化不少同学应该疑惑，dp[0] dp[1]应该初始化多少呢？

有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。

严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。

拆分0和拆分1的最大乘积是多少？

这是无解的。

这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！

确定遍历顺序确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

创建数组dp，长度是n+1，dp[i]表示数字i拆分后加数最大乘积；将前两个数字初始化为0，因为零和1都不能拆分。

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

1.22 分割等和子集

题目描述：

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

解题思路：参考代码随想录：如果要是能拆分成两个等和子集，说明和等于“数组之和除以2”

target=sum(ALL)//2动规五部曲分析如下：

确定dp数组以及下标的含义 01背包中，dp[i] 表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

套到本题，dp[i]表示背包总容量是i，最大可以凑成i的子集总和为dp[i]。

确定递推公式 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

dp数组如何初始化在01背包，一维dp如何初始化，已经讲过，

从dp[j]的定义来看，首先dp[0]一定是0。

如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

举例推导dp数组 dp[i]的数值一定是小于等于i的。

如果dp[i] == i 说明，集合中的子集总和正好可以凑成总和i，理解这一点很重要。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        taraget = sum(nums)
        if taraget % 2 == 1: return False
        taraget //= 2
        dp = [0] * 10001
        for i in range(len(nums)):
            for j in range(taraget, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        return taraget == dp[taraget]

1.23 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积

典型的动态规划，定义好状态

看到一个解析不错

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        max_side = 0
        dp = [[0] * cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                # 当前的值为 1 时，考虑求构成正方形的最长边
                if matrix[i][j] == '1':
                    # 当前值为 1，处于首行首列时，不考虑左，上，左上三个方向
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
                    max_side = max(max_side, dp[i][j])
        
        square = max_side ** 2
        return square

1.24 一和零

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3 输出：4

解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：输入：strs = [“10”, “0”, “1”], m = 1, n = 1 输出：2 解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 <= strs.length <= 600 1 <= strs[i].length <= 100 strs[i] 仅由 ‘0’ 和 ‘1’ 组成 1 <= m, n <= 100

解题思路

参考代码随想录

开始动规五部曲：

确定dp数组（dp table）以及下标的含义 dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

确定递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！只不过物品的重量有了两个维度而已。

dp数组如何初始化在动态规划：关于01背包问题，你该了解这些！（滚动数组）中已经讲解了，01背包的dp数组初始化为0就可以。

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

确定遍历顺序在动态规划：关于01背包问题，你该了解这些！（滚动数组）中，我们讲到了01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

代码如下：

有同学可能想，那个遍历背包容量的两层for循环先后循序有没有什么讲究？

没讲究，都是物品重量的一个维度，先遍历那个都行！

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 默认初始化0
        # dp=np.zero(m+1,n+1)
        # 遍历物品
        for str in strs:
            ones = str.count('1')
            zeros = str.count('0')
            # 遍历背包容量且从后向前遍历！
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        return dp[m][n]

1.25 最后一块石头一

题目描述每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：输入：[2,7,4,1,8,1] 输出：1 解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。提示： 1 <= stones.length <= 30 1 <= stones[i] <= 1000

解题思路

这个题和分割等和子集非常像了。

本题物品的重量为stone[i]，物品的价值也为stone[i]。

对应着01背包里的物品重量weight[i]和物品价值value[i]。

接下来进行动规五步曲：

确定dp数组以及下标的含义 dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。

确定递推公式 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

一些同学可能看到这dp[j - stones[i]] + stones[i]中又有- stones[i] 又有+stones[i]，看着有点晕乎。

还是要牢记dp[j]的含义，要知道dp[j - stones[i]]为容量为j - stones[i]的背包最大所背重量。

dp数组如何初始化既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。

而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

当然也可以把石头遍历一遍，计算出石头总重量然后除2，得到dp数组的大小。

我这里就直接用15000了。

接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])中dp[j]才不会初始值所覆盖。

有了递推公式，就很简单了

class Solution:
    def canPartition(self, stones: List[int]) -> bool:
        taraget = sum(stones)
        sum=0
        if taraget % 2 == 1: return False
        taraget //= 2
        dp = [0] * 10001
        for i in range(len(stones)):
            for j in range(taraget, stones[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        return sum - dp[target] - dp[target]

1.26 戳气球问题

题目描述

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量

输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [ ] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

解题思路

设dp[i][j]表示错破i到j之间的气球能得到的最大硬币数量。假设k是最后一个被戳破的气球，i<k<j ,于是乎，如果我们从k处把序列断开为(i,k)和(k,j) 那么 dp[i][j] = max(dp[i][k]+dp[k][j] + nums[i]nums[k]nums[j])

def maxCoins(iNums):
    nums = [1] + [i for i in iNums if i > 0] + [1]
    n = len(nums)
    dp = [[0]*n for _ in range(n)]

    for k in range(2, n):
        for left in range(0, n - k):
            right = left + k
            for i in range(left + 1,right):
                dp[left][right] = max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
    return dp[0][n - 1]

1.27 最后一块石头二

有时间再看

1.28 总结

动态规划问题解题思路

动态规划专题

动态规划专题

1 动态规划问题

1.1 解题思路

1.2 最大子序和问题

1.3 最长上升子序列

1.4 最长公共子序列长度

1.5 最长重复子数组长度

1.6 最短路径和问题

1.7 爬楼梯问题

1.8 母牛生产一

1.9 母牛生产二

1.10 不同路径

1.11 最长回文字符串

1.12 回文子字符串数量

1.13 最大乘积和

1.14 买卖股票专题

1.15 完全平方数

1.16 找零钱问题

1.17 单词切分

1.18 打家劫舍专题

1.18.1 打家劫舍一

1.18.2 打家劫舍二之环形房屋

1.18.3 打家劫舍三之二叉树房屋

1.19 编辑距离

1.20 鸡蛋掉落

1.21 整数拆分

1.22 分割等和子集

1.23 最大正方形

1.24 一和零

1.25 最后一块石头一

1.26 戳气球问题

1.27 最后一块石头二

1.28 总结