知识储备--基础算法篇-动态规划

1.前言

第一次接触动态规划，不知道具体什么意思，做了题才发现动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划。比如上楼梯，一次上一阶或二阶，求有多少种算法，就可以拆成最后一阶的方法数等于前一阶的方法数加前两阶的方法数，这就是递归算法。但是这样往往会超出时间限制，因为里面有大量的重复，比如一共5阶，F(5)=F(4)+F(3)，其中F(4)=F(3)+F(2)，这里面F(3)就被重复计算了，这时我们需要将算好的值储存下来，避免重复计算，这就是记忆递归算法。

所有的动态规划问题都可以归结为有向无环图的求解。

如何确定题目是搜索还是动态规划？可以先将状态抽象为节点，关系用边表示，想一下拓扑排序，如果有环，就不是动态规划，

动态规划一般是有固定的范围的，数据量有限。如果数据量很大，有可能是暴力搜索或贪心。

递归是一种程序的实现方式：函数的自我调用。

动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)

使用场景

满足两个条件

• 满足以下条件之一

  • 求最大/最小值（Maximum/Minimum ）

  • 求是否可行（Yes/No ）

  • 求可行个数（Count(*) ）

• 满足不能排序或者交换（Can not sort / swap ）

• 动态规划其实就是用空间换时间，一开始可以将动态规划题目抽象成树来递归，但是发现有许多重复计算的内容，这时用一个数组记录下计算过的值，这就是空间换时间，记忆化递归。
• 递推公式，也就是状态转移方程是核心，就是利用以往状态推导出当前状态。
• 一般按照以下步骤来：

1. 设计状态
2. 写出状态转移方程
3. 设置初始状态
4. 执行状态转移
5. 返回最后的解

2.实战

2.1第70题-爬楼梯

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

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

心得：很经典的题目，用动态规划，之前一直有个疑问就是，递归的顺序是怎么执行的，是同时计算同一层的两个F(n-1)和F(n-2)，还是先计算位于前面的F(n-1)，直到算出F(n-1)再计算F(n-2)，这次我直接打印出来了，发现是先递归计算出位于前面的F(n-1)，这时该储存的已经储存好了，后面计算F(n-2)时就不会重复计算了。

 改成自下而上dp（动态规划）

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1:
            return 1
        elif n==2:
            return 2
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[n]

因为该问题符合斐波那契数列，直接算

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = b = 1
        for i in range(2, n + 1):
            a, b = b, a + b
        return b

2.2第746题-使用最小花费爬楼梯

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

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

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

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        # 动态规划
        # dp[j]表示爬到第j个台阶的最小花费
        # 状态转移方程：dp[j]=min(dp[j-1]+cost[j-1], dp[j-2]+cost[j-2])
        # 初始化:dp[0]=0, dp[1] = 0
        dp = [1000]*(len(cost)+1)
        dp[0] = 0
        dp[1] = 0
        for i in range(2,len(cost)+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[-1]

2.3第118题-杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows==1:
            return [[1]]
        result = [[1]]
        for i in range(2,numRows+1):
            current = [1]*i
            if i>2:
                for j in range(1,i-1):
                    current[j] = result[i-2][j-1]+result[i-2][j]
            result.append(current)
        
        return result

2.4第198题-打家劫舍

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

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

心得：看到这种求最大金额的题目就要想到动态规划，动态规划就是要把大问题分为一个个的小问题来进行解决。这道题就是，可以把最高金额的问题分为求局部最高金额的问题，然后再递归就能解决了。感觉像是上楼梯的升级题目，多了一个max判断。自左往右。也可以使用递归，自右往左。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])
        dp = [0]*(len(nums)+1)
        dp[1] = nums[0]
        dp[2] = nums[1]
        for i in range(3,len(nums)+1):
            dp[i] = max(dp[i-3] + nums[i-1], dp[i-2] + nums[i-1])
        return max(dp[-1], dp[-2])

上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])
        dp = [0]*(len(nums)+1)
        left = nums[0]
        right = max(nums[0], nums[1])
        for i in range(3,len(nums)+1):
            left, right = right, max(left + nums[i-1], right)
        return right

2.5第213题-打家劫舍2

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

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

示例 1：

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

心得：不能同时取第一个和最后一个，那就使这两个中有一个为0，生成两个数组，一个第一个值是0，一个最后一个值是0。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 0-1背包
        # dp[j]表示以j为尾的数组偷到的最高金额
        # dp[j] = max(dp[j-1], dp[j-2] + nums[i])
        # 初始化：dp[0] = 0, dp[1] = nums[0]
        # 顺序：外层物品，内层背包逆序
        def repeat(nums):
            n = len(nums)
            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[-1]
        
        if len(nums) == 1:
            return nums[0]
        nums1 = copy.deepcopy(nums)
        nums1[0] = 0
        nums2 = copy.deepcopy(nums)
        nums2[-1] = 0
        a = repeat(nums1)
        b = repeat(nums2)

        return max(a,b)

2.6第337题-打家劫舍3

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

心得：暴力递归，超时。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 递归
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return root.val
        # 偷父节点
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # 不偷父节点
        val2 = self.rob(root.left) + self.rob(root.right)
        
        return max(val1, val2)

2.7第121题-买卖股票的最佳时机

2.8第122题-买卖股票的最佳时机2

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

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

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 滑动窗口，窗口大小为2，递增则加
        max_value = 0
        for i in range(len(prices)-1):
            cap = prices[i+1] - prices[i]
            if cap > 0 :
                max_value += cap
        
        return max_value

2.4第279题-完全平方数

完全背包问题

把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义，dp[j]：和为j的完全平方数的最少数量为dp[j]
2. 确定递推公式，dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
3. dp数组如何初始化，dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。有同学问题，那0 * 0 也算是一种啊，为啥dp[0] 就是 0呢？看题目描述，找到若干个完全平方数（比如 1, 4, 9, 16, ...），题目描述中可没说要从0开始，dp[0]=0完全是为了递推公式。非0下标的dp[j]应该是多少呢？从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
4. 确定遍历顺序，我们知道这是完全背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
5. 举例推导dp数组

所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

我这里先给出外层遍历背包，内层遍历物品的代码：

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [10]*(n+1)
        dp[0] = 0
        for i in range(n+1):
            j = 1
            while j*j <= i:
                dp[i] = min(dp[i-j*j]+1, dp[i])
                j = j + 1
        return dp[n]

 外层遍历物品，内层遍历背包的代码：

因为是完全背包，所以外层的物品可以有很多个，内层就可以一直装。

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [10]*(n+1)
        dp[0] = 0
        i = 1
        while i * i <= n:
            j = i * i
            while j <= n:
                dp[j] = min(dp[j-i*i]+1, dp[j])
                j = j + 1
            i = i + 1
        return dp[n]

2.5第322题-零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

心得：又是完全背包的题，按照上面的动规五部曲，

1. 确定dp[j]的含义，dp[j]是当背包容量（也就是amount）为j时，最少的硬币个数。
2. 递归公式为dp[j]=min(dp[j-coin]+1, dp[j])
3. 初始化，当总金额为0时，需要的硬币个数为0，所以dp[0]=0。又因为求最小，所以初始化dp中都存入最大值float('inf')。
4. 确定遍历顺序，组合就外面物品，里面背包。
5. 举例推导dp数组。比如dp[5]。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount==0:
            return 0
        dp = [float('inf')]*(amount+1)
        dp[0] = 0
        # 完全背包
        # 组合，外层物品，内层背包
        for i in range(len(coins)):
            coin = coins[i]
            j = coin
            while j <= amount:
                dp[j] = min(dp[j-coin]+1, dp[j])
                j = j + 1
        if dp[amount]==float('inf'):
            return -1
        else:
            return dp[amount]

2.6第139题-单词拆分

给你一个字符串 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

心得：想的是直接暴力排序，不断递归循环，匹配上的就切掉，剩余的继续递归，直到循环完毕。但是最后超时了，给了一个离谱的例子。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # 背包问题
        # s是背包，wordDict是物品
        # 完全背包问题
        # 排列问题，外层用背包，内层用物品
        def dp(str, wordDict):
            if str == '':
                return True
            for i in range(len(wordDict)):
                a = str[:len(wordDict[i])]
                # print(a, wordDict[i])
                if a == wordDict[i]:
                    if dp(str[len(wordDict[i]):], wordDict):
                        return True
                    else:
                        continue
                else:
                    continue
            return False
        
        return dp(s, wordDict)
        

看了题解才写出来，坚持动规五部曲，主要第一步关于dp[i]的含义没想到还能这样抽象，始终以题目的结果来作为dp[i]的含义（该题dp[i]就是以长度为i（必须是数字）的字符是否能由字典里的单词组成）还有就是循环也可以是字符串，递推公式也不是很好想。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # 背包问题
        # s是背包，wordDict是物品
        # 完全背包问题
        # 排列问题，外层用背包，内层用物品
        len_ = len(wordDict)
        i = 0
        j = 0
        # 1.dp[i]是当背包容量(字符串长度)为i时，True表示可以拆分为一个或多个单词
        # 2.if dp[i-j]为True且[i,j]有单词存在，则dp[i]也为True
        # 3.dp[0]=True
        # 4.循环顺序，排列问题，外层用背包，内层用物品
        # 5.举例，leetcode长度为8，
        dp = [False]*(len(s)+1)
        dp[0] = True
        for i in range(1,len(s)+1):
            for word in wordDict:
                if s[i-len(word):i]==word:
                    # print(i, word)
                    if dp[i]==False:
                        dp[i] = dp[i-len(word)]
        # print(dp)
        return dp[-1]


        

第二遍刷：感受很多，初始条件一定要注意，状态要设计好，状态转移方程想好。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # 动态规划
        # 设计状态：dp[i]表示以i为尾的子字符串能否由字典拼出
        # 状态转移方程：若dp[i-j]为true, 且s[j:i] in wordDict, 则dp[i]为True, j为len(wordDict[])
        # 初始状态：dp[0]=True
        # 存到哈希表中，查找比列表快很多
        hash_table = set(wordDict)
        dp = [False]*(len(s)+1)
        dp[0] = True
        for i in range(1,len(s)+1):
            j = 0
            while j < len(wordDict):
                if i-len(wordDict[j]) >= 0:
                    if dp[i-len(wordDict[j])] and (s[i-len(wordDict[j]):i] in hash_table):
                        dp[i] = True
                j += 1
        
        return dp[-1]

2.7第300题-最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

心得：自己没做出来，主要是卡在了递推公式上，一直想的dp[i]=dp[i-j]，递推公式中的j其实也是可以循环来变化的，还有就是过于关注nums[j]>nums[i]的情况了，其实就直接找最长的就可以。多半带max。

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 完全背包问题
        # 排列
        # 1.dp[i]为当数组长度为i时(以nums[i-1]为结尾的数组)，最长严格递增子序列的长度
        # 2.递推公式，j<i,当nums[j]<nums[i]时，dp[i]=max(dp[j]+1, dp[i])
        # 3.初始化，dp[0]=1,dp=1*(len(nums)+1)
        # 4.循环顺序,排列，外层物品，内层背包
        # 5.举例，[0,1,0,3,2,3]
        dp=[1]*(len(nums))
        max_len = 1
        for i in range(1,len(nums)):
            j = 0
            while j < i:
                if nums[j]<nums[i]:
                    dp[i]=max(dp[j]+1, dp[i])
                j = j + 1
            if max_len<dp[i]:
                max_len = dp[i]

        return max_len

刷第二遍，还是倒在了状态转移方程，还是没考虑到j的变化，！！！ 

2.8第152题-乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

心得：想了半天递推公式还是没写对，只能暴力遍历了，果然超时。还有就是列表的拷贝需要用深拷贝copy.deepcopy(list)，不然会修改原始列表的值。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 连续，nums是物品，最大子数组的乘积是背包
        # 1.dp[i]是最大乘积子数组对应乘积max，i是nums[i]为尾的子数组
        # 2.递推公式：dp[i]=max(nums[j]*(nums[j+1]...nums[i]), dp[i])
        # 3.初始值：dp[0]=nums[0], dp=[1]*len(nums)
        # 4.循环顺序：排序，外层物品。内层背包。
        # 5.示例：[2,3,-2,4]
        dp = copy.deepcopy(nums)
        # dp[0] = nums[0]
        max_ = dp[0]
        for i in range(1,len(nums)):
            j = 0
            while j < i:
                a = 1
                for k in range(j,i+1):
                    a = a * nums[k]
                dp[i] = max(a, dp[i])
                j = j + 1
            if max_ < dp[i]:
                max_ = dp[i]
        print(dp)
        return max_

看了解析，知道了由于会出现负数相乘的情况，所以需要同时维护最大值和最小值，结果如下

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 连续，nums是物品，最大子数组的乘积是背包
        # 1.dp[i]是最大乘积子数组对应乘积max，i是nums[i]为尾的子数组
        # 2.递推公式：
        # dp_max[i]=max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp[i])
        # dp_min[i]=min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp[i])
        # 3.初始值：dp[0]=nums[0], dp=[1]*len(nums)
        # 4.循环顺序：排序，外层物品。内层背包。
        # 5.示例：[2,3,-2,4]
        dp_max = copy.deepcopy(nums)
        dp_min = copy.deepcopy(nums)
        max_ = nums[0]
        for i in range(1,len(nums)):
            j = 0
            dp_max[i]=max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp_max[i])
            dp_min[i]=min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp_min[i])
            if max_ < dp_max[i]:
                max_ = dp_max[i]
            elif max_ < dp_min[i]:
                max_ = dp_min[i]
        return max_

发现最大值和最小值根本就不用列表来表示，因为只用到了前一个max和min，所以直接用两个变量来表示，时间和内存都大大降低。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 连续，nums是物品，最大子数组的乘积是背包
        # 1.dp[i]是最大乘积子数组对应乘积max，i是nums[i]为尾的子数组
        # 2.递推公式：
        # dp_max[i]=max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp[i])
        # dp_min[i]=min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], dp[i])
        # 3.初始值：dp[0]=nums[0], dp=[1]*len(nums)
        # 4.循环顺序：排序，外层物品。内层背包。
        # 5.示例：[2,3,-2,4]
        dp_max = nums[0]
        dp_min = nums[0]
        max_ = nums[0]
        for i in range(1,len(nums)):
            dp_max_before = dp_max
            dp_min_before = dp_min
            dp_max=max(dp_max_before*nums[i], dp_min_before*nums[i], nums[i])
            dp_min=min(dp_max_before*nums[i], dp_min_before*nums[i], nums[i])
            if max_ < dp_max:
                max_ = dp_max
            elif max_ < dp_min:
                max_ = dp_min
        return max_

2.9第416题-分割等和子集

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

心得：看了解析也还是没懂，去看了代码随想录的视频，感觉讲的还是很不错的，不过光听不行，还是得自己写一遍，把dp列表打印出来看才能完全掌握，代码中已经写好注释。 

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 可以看作是0-1背包问题
        # 题目可以抽象为在nums中寻找一个子数组，要求最大价值为总和的一半
        # 该题的重量和价值是一样的
        # 1.dp[j]为背包容量为j时(这里背包的容量和最大价值是一样的，都为总和的一半)，子数组的最大价值。
        # 2.递推公式：dp[j]=max(dp[j], dp[j-weight[i]]+value[i])
        # 3.初始化：dp[0]=0, dp=[0]*(len(nums)+1)
        # 4.循环顺序：外层物品正序，内层背包容量倒序(因为是0-1背包，正序的话会重复计算)
        # 5.举例：[1,5,11,5]
        if sum(nums)%2 == 1:
            return False
        target = sum(nums)/2
        dp = [0]*(target+1)
        # 先拿出第一个物品，然后背包的容量递减，看看每个容量怎么装
        # 再放下第一个物品拿出第二个，背包容量再次从target递减，看看现在背包里还能放下吗，最大放多少
        # 依次按顺序拿出物品
        for i in range(len(nums)): # 物品
            j = target
            while j >= nums[i]: # 背包容量要大于物品
                dp[j]=max(dp[j], dp[j-nums[i]]+nums[i]) # 取max是因为最大也不会超过背包的容量target
                if dp[j] == target:
                    return True
                j = j - 1
        return False

2.10第1049题-最后一块石头的重量2

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [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]，这就是最优值。

心得：靠，还是没把题目转化成做过的题，老是想着怎么用之前的状态推出最后的结果。结果题就没读懂，只需要把数组尽量分成两个相同的堆就好了。 

最后用sum-dp[target]*2时间复杂度更低。target是总和的一半。

class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        # 动态规划
        # 尽量把数组分成两个相同的堆。
        # dp[j]为背包容量为j时的最大价值。背包容量为j，物品重量为stones[i]，物品价值也为stones[i]。
        # dp[j]=max(dp[j], dp[j-weight[i]]+value[i])
        sum_stones = 0
        for i in range(len(stones)):
            sum_stones += stones[i]
        
        dp = [0]*(sum_stones+1)
        min_weight = 100000
        # 外层物品，内层背包且倒序
        for i in range(len(stones)):
            for j in reversed(range(sum_stones+1)):
                if j >= stones[i]:
                    dp[j] = max(dp[j], dp[j-stones[i]] + stones[i])
                    if abs(sum_stones - 2*dp[j]) < min_weight:
                        min_weight = abs(sum_stones - 2*dp[j])
                    elif sum_stones - 2*dp[j] == 0:
                        return 0
        
        return min_weight

2.11第494题-目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

心得：真的不知道咋做，一看答案，还是抽象能力太差了。 

这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。

本题则是装满有几种方法。其实这就是一个组合问题了。

1、确定dp数组以及下标的含义:dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法。

 2、确定递推公式

有哪些来源可以推出dp[j]呢？

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # left = (target + sum)/2，求左边的组
        sum_nums = 0
        for i in range(len(nums)):
            sum_nums += nums[i]
        left_sum = (target + sum_nums)/2
        if abs(target) > sum_nums:
            return 0
        if (target + sum_nums)%2 == 1:
            return 0
        # dp[j]表示背包容量为j时，有dp[j]种方法
        # dp[j] += dp[j-nums[i]]
        # 初始化：dp[0] = 1, 初始化主要看递推公式，当递推公式出现0时应该给多少。
        dp = [0]*(left_sum+1)
        dp[0] = 1
        # 先物品后背包，先顺序后倒序
        for i in range(len(nums)):
            for j in reversed(range(left_sum+1)):
                if j >= nums[i]:
                    dp[j] += dp[j-nums[i]]
        
        return dp[-1]

2.12第474题-一和零

给你一个二进制字符串数组 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 。

心得：其实就是多维背包，没什么特别的。 

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        # 0-1背包
        # dp[i][j]表示0的容量为i，1的容量为j时的最长子集长度
        # dp[i][j] = dp[i-sub_m][j-sub_n] + 1
        # 初始化：dp[0][0] = 0
        store = []
        for i in range(len(strs)):
            count_0 = 0
            count_1 = 0
            for j in range(len(strs[i])):
                if int(strs[i][j]) == 0:
                    count_0 += 1
                elif int(strs[i][j]) == 1:
                    count_1 += 1
            store.append([count_0, count_1])
        
        dp = []
        for i in range(m+1):
            dp.append([])
            for j in range(n+1):
                dp[i].append(0)
        for k in range(len(store)):
            for i in reversed(range(m+1)):
                for j in reversed(range(n+1)):
                    # print(i,j,store[k][0],store[k][1])
                    if i >= store[k][0] and j >= store[k][1]:
                        dp[i][j] = max(dp[i][j], dp[i-store[k][0]][j-store[k][1]] + 1)

        return dp[-1][-1]

2.13第518题-零钱兑换2

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        # 无限个，表示完全背包
        # dp[j]表示背包容量为j时的组合数，背包容量最大为amount，物品重量coins[i]，物品价值coins[i]
        # dp[j] += dp[j-weight[i]]
        # 初始化：dp[0] = 1
        dp = [0]*(amount+1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(amount+1):
                if j >= coins[i]:
                    dp[j] += dp[j - coins[i]]
        
        return dp[-1]

2.14第377题-组合总和4

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

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

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

心得：看似是一个组合题，但是顺序不同被视为不同的组合，所以其实还是一个排列题，外层必须是背包，内层是物品。 

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 无限个，完全背包
        # dp[j]表示容量为j时的组合数，背包容量最大为target，物品重量nums[i]，价值nums[i]
        # dp[j] += dp[j-nums[i]]
        # 初始化：dp[0] = 1
        dp = [0]*(target+1)
        dp[0] = 1
        for j in range(target+1):
            for i in range(len(nums)):
                if j >= nums[i]:
                    dp[j] += dp[j-nums[i]]
        
        return dp[-1]

3.0-1背包

背包问题和传统的动态规划题目不太一样，虽然都用到了状态之间的转移，但是传统的动态规划题目dp[ j ]中的 j 和dp[ j ]的含义都各不一样，常常为题目要求的答案，而背包问题往往都需要抽象成背包容量为 j 时的最大价值。

1. 先确定含义，包括背包的容量，物品的重量和价值。
2. 设计dp[i][j]的意义，从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
3. 状态转移方程：dp [ i ][ j ] = max ( dp [ i - 1 ][ j ], dp [ i - 1 ] [ j - weight [ i ] ]+value[ i ] )
4. 初始化dp数组：dp [ i ][ 0 ] = 0，dp [ 0 ][ j ]需要初始化，当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
5. 确定遍历顺序：都可以！！ 但是先遍历物品更好理解。

给出先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

先遍历背包，再遍历物品

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

最后一步就是举例推导dp数组了，最好再打印一下dp数组，看是否与设计的一致。

3.1一维dp数组（滚动数组）

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

1. 确定dp数组的定义：在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2. 一维dp数组的递推公式：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

 可以看出相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。

     3.一维dp数组如何初始化：dp[0] = 0，其他非零下标按照题目来，一般都为0，但是需要结合题目，能够被覆盖掉才行。

     4.一维dp数组遍历顺序：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

4.完全背包

完全背包是0-1背包的一种特殊情况

0-1背包和完全背包唯一不同就是体现在遍历顺序上。

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
    cout << endl;
}

如果题目设计有几种取的方式，这里在遍历顺序上可就有说法了。

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

4.多维动态规划

4.1第62题-不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

心得：回溯暴搜，结果超时 

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        right = 1
        down = 1
        # 机器人横着需要走n-1步，竖着需要走m-1步
        # 一共需要走n+m-2步。每一步都有两个状态，右或者下
        # 回溯，或者递归
        def dfs(right, down):
            if (right + down) == m+n:
                self.result += 1
                return
            
            if right < n:
                dfs(right + 1, down)
            if down < m:
                dfs(right, down + 1)
            
            right -= 1
            down = 0
            return

        self.result = 0
        dfs(right, down)
        
        return self.result

看了解析，发现每一个结点的路径都可以由左边或上边的节点推出来，竟然没想到。

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        right = 1
        down = 1
        # 机器人横着需要走n-1步，竖着需要走m-1步
        # 一共需要走n+m-2步。每一步都有两个状态，右或者下
        # 动规，使用动规的时候一定要想题目的问题。
        # 求到(m,n)有多少条不同的路径，子问题就是到(m-1,n)有多少条...
        # 用二维dp，dp[i][j]表示从(0,0)到(i,j)有dp[i][j]条路径
        # 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # 初始化：dp[0][j] = 1, dp[i][0] = 1
        dp = []
        for i in range(m):
            dp.append([])
            for j in range(n):
                if i == 0:
                    dp[i].append(1)
                elif j == 0:
                    dp[i].append(1)
                else:
                    dp[i].append(0)
        
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        # print(dp)
        return dp[m-1][n-1]

4.1.1创建二维列表

使用嵌套的for循环创建二维列表

s = []                  # 创建一个空列表
for i in range(5):      # 创建一个5行的列表（行）
    s.append([])        # 在空的列表中添加空的列表
    for j in range(5):  # 循环每一行的每一个元素（列）
        s[i].append(j)  # 为内层列表添加元素

使用列表推导式创建二维列表。

s = [[j for j in range(5)] for i in range(5)]

4.2第63题-不同路径2

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

心得：没注意看题，障碍物可能会有多个，初始化的时候要注意。正式递推时要从（1,1）开始。

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        # 动态规划
        # dp[i][j]表示到达(i,j)有多少种不同的路径
        # dp[i][j] = dp[i-1][j] + dp[i][j-1]
        # 初始化：障碍物的dp为0，若障碍物在上边沿和左边沿，则障碍物右边或下边的都初始化为0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = []
        # 初始化
        for i in range(m):
            dp.append([])
            for j in range(n):
                dp[i].append(0)
        flag = True
        if obstacleGrid[0][0] != 1:
            for i in range(m):
                for j in range(n):
                    if i == 0:
                        if obstacleGrid[i][j] == 1:
                            break
                        dp[i][j] = 1
                    elif j == 0:
                        if obstacleGrid[i][j] == 1:
                            flag = False
                            break
                        if flag:
                            dp[i][j] = 1
        
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

4.3第343题-整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

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

心得：递推公式中忽略了还可以乘上拆分的数本身的情况。 

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 动态规划
        # dp[j]为正整数j的最大乘积
        # dp[j]=max(dp[j-i]*i, dp[j])
        # 初始化：dp[0]=0, dp[1]=1
        dp = [0]*(n+1)
        dp[1] = 1
        for j in range(2,n+1):
            i = 1
            while i < j:
                dp[j]=max(dp[j-i]*i, dp[j], (j-i)*i)
                i += 1

        return dp[-1]

4.4第96题-不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

心得：我觉得主要还是找到规律，也就是递推公式想明白了就很好做。 

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 分别以每个数字作为根节点，每个子树也遵循，其实节点数量相同的树，二叉搜索树种类也相同
        # dp[i]表示i个节点有多少种二叉搜索树
        # dp[i] += dp[j]*dp[i-j-1]
        # 初始化：dp[0] = 0, dp[1]=1, dp[2] = 2
        if n == 2:
            return 2
        elif n == 1:
            return 1
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            j = 0
            while j < i:
                dp[i] +=  dp[i-j-1]*dp[j]
                j += 1
        
        return dp[-1]

4.2第64题-最小路径和

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

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

示例 1：

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

心得：不同路径就是为这道题铺路的。

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 和不同路径很像啊
        m = len(grid)
        n = len(grid[0])
        # dp[i][j]为到达(i,j)的最小数字总和
        dp = []
        for i in range(m):
            dp.append([])
            for j in range(n):
                if i == 0:
                    if j == 0:
                        dp[i].append(grid[i][j])
                    else:
                        dp[i].append(dp[i][-1] + grid[i][j])
                elif j == 0:
                    dp[i].append(dp[i-1][j] + grid[i][j])
                else:
                    dp[i].append(0)
        
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])

        return dp[m-1][n-1]

4.3第五题-最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

心得：直接暴力滑动窗口，差点超时。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 最长可以分为小问题解决吗
        # 0-1背包
        # dp[j]为背包容量为j时，最长的回文子串
        # 滑动窗口？
        if len(s) == 1:
            return s
        result = []
        for i in range(len(s)+1):
            for j in range(len(s)):
                if j+i <= len(s):
                    temp = s[j:j+i]
                    if temp == temp[::-1]:
                        result.append(temp)
                        break
        
        return result[-1]

一想，根本不需要存储，只需要找到最长的子序列就行了，优化一下。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 最长可以分为小问题解决吗
        # 0-1背包
        # dp[j]为背包容量为j时，最长的回文子串
        # 滑动窗口？
        for i in reversed(range(len(s)+1)):
            for j in range(len(s)):
                if j+i <= len(s):
                    temp = s[j:j+i]
                    if temp == temp[::-1]:
                        return temp

4.4第1143题-最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

心得：想了半天想出个方法，但是只能应用到没有重复字母的字符串上。 

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        # 思考问题，最终的结果是ace, 那么ace如何由之前的状态推导出来，那么就是abc和ac的最长公共子序列推导出来的
        # 建立一个字典，存储短字符串的字母和索引，如果长字符串的每个字符在字典中，且索引大于前一个，则加一
        dict_text = {}
        a = len(text1)
        b = len(text2)
        max_len = 0
        temp = -1
        result = []
        if a <= b:
            for i in range(a):
                dict_text[text1[i]] = i
            for j in range(b):
                if text2[j] in dict_text:
                    result.append(dict_text[text2[j]])
        else:
            for i in range(b):
                dict_text[text2[i]] = i
            for j in range(a):
                if text1[j] in dict_text:
                    result.append(dict_text[text1[j]])
        
        print(result)
        if result == []:
            return 0
        # 问题改成了求最长递增子序列长度
        # dp[j]表示以j为尾的最长递增子序列长度
        # dp[j]=max(dp[i], dp[j])
        # 初始化dp[0]=1, dp = [0]*(len(result)+1)
        dp = [1]*len(result)
        for i in range(len(result)):
            j = 0
            while j < i:
                if result[i] > result[j]:
                    dp[i]=max(dp[j] + 1, dp[i])
                j += 1
        
        print(dp)
        return max(dp)

看了解析，发现并不难理解，就是自己想不到。

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        # 思考问题，最终的结果是ace, 那么ace如何由之前的状态推导出来，那么就是abc和ac的最长公共子序列推导出来的
        m, n = len(text1), len(text2)
        dp = [0] * (n + 1)  # 初始化一维DP数组
        
        for i in range(1, m + 1):
            prev = 0  # 保存上一个位置的最长公共子序列长度
            for j in range(1, n + 1):
                curr = dp[j]  # 保存当前位置的最长公共子序列长度
                if text1[i - 1] == text2[j - 1]:
                    # 如果当前字符相等，则最长公共子序列长度加一
                    dp[j] = prev + 1
                else:
                    # 如果当前字符不相等，则选择保留前一个位置的最长公共子序列长度中的较大值
                    dp[j] = max(dp[j], dp[j - 1])
                prev = curr  # 更新上一个位置的最长公共子序列长度
        
        return dp[n]  # 返回最后一个位置的最长公共子序列长度作为结果

5.总结

非背包问题：以题目的返回值作为dp[ j ]的含义。

背包问题

通常dp[ j ]的含义是装满容量为 j 的背包的最大价值，有几种方法。文章来源地址https://www.toymoban.com/news/detail-665394.html

1. 确定背包类型，0-1还是完全
2. 明确含义，背包容量，物品重量，物品价值分别是什么
3. 设计状态：dp[j]，j的意义，dp[j]的意义
4. 状态转移方程：dp[j]=max(dp[j], dp[j-weight[i]]+value[i])
5. 初始化：dp[0]=0, 非零下标初始化为多少
6. 遍历顺序，0-1背包时，外层物品，内层背包，内层反循环。完全背包时，如果组合，则外层物品，内层背包，如果排列，则外层背包，内层物品，都是正循环。

到了这里，关于知识储备--基础算法篇-动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！