中等难度-动态规划

来自leetcode题目：5,62,64,96,139,152,221,279,300,309,322,338,416,494,647

动态规划问题：
1. 定义状态：
  即定义数据元素的含义
2. 建立状态转移方程：
3. 设定初始值：
4. 状态压缩：
  即优化数组空间，每次状态的更新只依赖于前一次的状态，优化一般作用于多维数组，
  观察是否可以将多维数组以一维数组来动态表示，即用一维数组来保存上次的状态。
5. 选出结果(返回值)

5.最长回文子串

题目描述：
- 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"

python二维数组的创建

#[[0]*3]*3的方式是不可行的，浅拷贝的数组指向同一个内存
list_three = [[0]*3]*3
print(list_three) #结果为[0,0,0],[0,0,0],[0,0,0]
list_three[1][1]=2
print(list_three)#[0,2,0],[0,2,0],[0,2,0]
#所以以上的方式是不可行的
list_three = [[0 for i in range(3)] for j in range(3)]
list_three[1][1] = 2
print(list_three)#[0,0,0],[0,2,0],[0,0,0]

题解：来自liweiwei大佬

class Solution:
    def longestPalindrome(self, s: str) -> str:
        '''
        如果字符串的首尾两个字符不相等，那么不是回文
        如果首尾字符相等，再判断里面的子串，缩小规模，判断整体是否是回文
        i,j为要判断的某段字符串的左右下标
        dp[i][j] => s[i]-s[j]
        dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
        i和j的关系应该是i<=j
        dp[i+1][j-1]的边界条件是[i+1,j-1]不构成区间，即长度小于2
        即j - 1 - (i + 1) +1 < 2,也就是j - i < 3 (下标关系)
        所以i到j的长度要满足j - i + 1 < 4 
        所以当子串的长度等于2或者等于3的时候，只要判断首尾的字符是否相等即可
        所以如果同时满足s[i] == s[j] 和 j - i < 3的前提下，
            dp[i][j] = true
        可以肯定的有dp[i][i] = true
        只要得到dp[i][j] = true就记录子串的长度和起始位置
        '''
        size = len(s)
        #如果只有一个肯定是回文
        if size < 2:
            return s
        #创建一个二维数组
        dp = [[False for i in range(size)] for j in range(size)]
        #初始一个默认值
        max_len = 1
        start = 0
        for i in range(size):
            dp[i][i] = True
        for j in range(1,size):#j为终止位置
            for i in range(0,j):#i为起始位置
                if s[i] == s[j]:
                    #如果同时满足，则为true
                    if j - i < 3:
                        dp[i][j] = True
                    #如果只满足s[i]=s[j]则缩小规模
                    else:
                        #j是终止位置，所以某个字符串到j-1是否为回文肯定已经判断过了
                        dp[i][j] = dp[i+1][j-1]
                else:#s[i] != s[j]则不是回文
                    dp[i][j] = False
                #如果i->j是回文
                if dp[i][j]:
                    cur_len = j - i +1#长度
                    #如果当前回文长度比已保存的最大长度更长，则更新值保存长度以及起始位置
                    if cur_len > max_len:
                        max_len = cur_len
                        start = I
        #起点下标为start，终点下标为start+长度-1，所以截取[start:start+max_len]
        return s[start:start+max_len]

62.不同路径

题目描述：
- 一个机器人位于一个 m x n 网格的左上角
  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角
  问总共有多少条不同的路径？
示例：

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
(1) 向右 -> 向右 -> 向下
(2)向右 -> 向下 -> 向右
(3) 向下 -> 向右 -> 向右

题解：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        '''
        dp[i][j]: i表示列，j表示行
        机器人只能向右或者向下移动
        所以dp[i][j] = dp[i-1][j] + dp[i][j-1]
        '''
        f = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            f[i][0] = 1
        for j in range(n):
            f[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                f[i][j] = f[i-1][j] + f[i][j-1]
        return f[m-1][n-1]

64.最小路径和

题目描述：
- 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
  说明：每次只能向下或者向右移动一步。
示例：

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

题解

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        '''
        dp[i][j]表示到[i][j]的最小路径和
        只能向右或者向下走
        如果i!=0,j!=0:
            dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        如果i=0,j!=0:
            dp[i][j] = dp[i][j-1] + grid[i][j]
        如果i!=0,j=0:
            dp[i][j] = dp[i-1][j] + grid[i][j]
        如果i=0,j=0:
            dp[i][j] = grip[i][j]
        可以直接将dp矩阵的值覆盖到原grip矩阵，因为遍历过的元素不会再用到了
        所以没必要新建一个dp矩阵浪费空间
        '''
        for i in range(len(grid)):#grip的长度，也就是行
            for j in range(len(grid[0])):#列
                if i == j == 0: 
                    #覆盖到原矩阵上，又因为grid[i][j] = grid[i][j]，所以continue
                    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]

96.不同的二叉搜索树

题目描述：
- 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例：

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题解：

class Solution:
    def numTrees(self, n: int) -> int:
        '''
        假设f(n) = 有n个数字可以构建几种搜索树
        f(0) = 1 理解为没有数字就只有为空的一种情况
        f(1) = 1
        f(2) = 2
        当n=3时：
        (1)如果1为树根，左边有f(0)种情况，右边f(2)种情况，一共有f(0)*f(2)
        (2)如果2为树根，左边有f(1),右边f(1),共有f(1)*f(1)
        (3)如果3为树根，则共有f(2)*f(0)
        即f(3) = f(0)*f(2) + f(1)*f(1) + f(2)*f(0)
        同理：
        f(4) = f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)
        每一项两个f()中的数字加起来都等于n-1
        根据已知f(0),f(1)
        可以自底向上逐步得到f(n)的值
        '''
        nums = [1,1] #f(0),f(1)
        if n<= 1:
            return nums[n]
        for m in range(2,n+1):
            s = m-1  #两个f()中的数字之和等于m-1
            count = 0
            for i in range(m):
                count += nums[i]*nums[s-i]
            nums.append(count)
        return nums[n]

139.单词拆分

题目描述：
- 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
  说明：
  拆分时可以重复使用字典中的单词。
  你可以假设字典中没有重复的单词。
示例

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

题解：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n=len(s)
        #dp=[False...False] 长度为n+1
        dp=[False]*(n+1)
        dp[0]=True#dp[0]为True，空字符可以匹配
        for i in range(n):#i为开始下标
            for j in range(i+1,n+1):#j为结束下标
                #dp[i]=True则证明前i位可以匹配
                #s[i:j] in wordDict则表示i-j也可以匹配，所以前j位可以成功匹配
                if(dp[i] and (s[i:j] in wordDict)):
                    dp[j]=True
        #返回最后一位是否可以成功匹配即可
        return dp[-1]

152.乘积最大子数组

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

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

题解

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        # 结果变量初始化
        res = nums[0]  
        #初始化当前的最大值、最小值
        pre_max, pre_min = nums[0], nums[0]
        for i in range(1, len(nums)):
            left = nums[i] * pre_max
            right = nums[i] * pre_min
            # 因为当前nums[i]可正可负，所以得到的left，right大小关系不确定
            pre_max = max(left, right, nums[I])
            pre_min = min(left, right, nums[I])
            #保存结果变量
            res = max(res, pre_max)
        return res

221.最大正方形

题目描述：
- 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例：

题解

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        '''
        dp[i][j] 表示以matrix[i][j]为右下角的顶点的可以组成的最大正方形的边长
        if matrix[i][j] == 0: return 0
        if matrix[i][j] == 1: 将martix[i][j]往左和往上延伸
        要取另外三个点的最小值然后+1，只有最小值才是能与[i][j]一起构成新正方形的
        dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        '''
        res = 0
        if len(matrix) == 0 or len(matrix[0]) == 0 :
            return 0
        # 不知道为何，这两句放到前面就报错，无解，测试用例能过，提交就报错
        m = len(matrix)# 行
        n = len(matrix[0])# 列        
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                # 如果当前值为1，则判断当前位置所能组成的最大正方形边长，
                # 如果当前值不为1，则租不成正方形不去判断，二维数组默认值都为0
                if matrix[i][j] == '1':
                    # 如果i或者j为0，则在边上，最大边长只能为1
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:# 不在边上则计算其最大边长
                        dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
                    res = max(res,dp[i][j])
        return res**2

279.完全平方数

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

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

题解：

class Solution:
    def numSquares(self, n: int) -> int:
        '''
        dp[i]表示最少可以由几个平方数构成
        初始化dp=[0,1,2,...,n],长度为n+1，最多次数就是全部由1构成
        遍历dp，对于i，遍历区间[2,n+1)即2 -> n
        遍历所有平方数小于i的数j，遍历区间[1,int(√i)+1） 即1 -> int(√i)
            dp[i] = min(dp[i],dp[i-j*j]+1),始终保存所有可能情况的最小值
            dp[i-j*j]+1就跟找零问题类似，减去所有小的平方数，找到剩下的数所需的最小值
        '''
        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[n]

300.最长上升子序列

题目描述：
- 给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例

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

题解

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        '''
        子序列并不要求连续!!!!
        dp[i]表示nums前i个数字的最长子序列长度
        当0<=j<i，每轮计算dp[i]时，遍历[0,i)区间：
            nums[i]>nums[j]时，子序列长度为dp[j]+1
            nums[i]<=nums[j]时，上升子序列不成立
        dp[i] = max(dp[j]+1,dp[i])
        
        '''
        if not nums:
            return 0
        # 初始状态都为1，每个数字都可以单独作为一个子序列
        dp = [1] * len(nums)
        for i in range(1,len(nums)):
            for j in range(i):
                #因为要求严格递增，所以不能小于等于
                #nums[i]>nums[j]，则nums[i]可以接到nums[j]后边
                #其长度为以nums[j]结尾的子序列长度+1
                if nums[j] < nums[I]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

309.最佳买卖股票时期含冷冻期

题目描述：
- 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
  你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''
        取n = len(prices)，以[0,0]对n进行循环得到二维数组
        dp[i][j]: i代表天数，j代表是否持股(0，1)
        dp[i][0]:第i-1天不持股或者第i-1天持股但是第i天卖出了
        dp[i][1]:因为要有冷冻期，所以这里不是单纯第i-1天持股或者
                第i-1天不持股但是第i天持股
        所以第i天持股，可能是第i-1天持股，如果i-1不持股，那么i-2肯定也是不持股的
        '''
        n = len(prices)
        if not n or n < 2:
            return 0
        dp = [[0,0] for i in range(n)]
        # 初始化
        dp[0][0] = 0 # 第0天不持股则利润为0
        dp[0][1] = -prices[0] #第0天持股则为-prices[0]
        # 第一天不持股，要么是第0天不持股，要么就是第0天持股，第一天卖了
        dp[1][0] = max(dp[0][0],dp[0][1]+prices[1])
        # 第一天持股，要么是第一天持股，要么是第0天不持股第一天持股
        dp[1][1] = max(dp[0][1],dp[0][0]-prices[1])
        # 分别计算每一天持股与不持股的最大利润
        for i in range(2,n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[I])
            dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[I])
        #返回最后一天不持股的利润，因为最后一天不持股肯定比持股利润高
        return dp[-1][0]

322.零钱兑换

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

示例：

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

题解

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        f = [float('inf')]*(amount+1)
        f[0] = 0
        for c in coins:  # 枚举硬币种数
            for j in range(c, amount+1):  # 从小到大枚举金额，确保j-c >= 0.
                f[j] = min(f[j], f[j - c] + 1)
        # 如果为inf说明状态不可达，返回-1即可。
        return f[amount] if f[amount] != float('inf') else -1

338.比特位计数

题目描述：
- 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例

image.png
题解：

class Solution:
    def countBits(self, num: int) -> List[int]:
        '''
        二进制的特性：
            奇数的二进制中1的个数 = 它上一位偶数的二进制中1的个数 + 1
            偶数的二进制中1的个数 = (这个偶数 // 2)得到的数的二进制中1的个数
        '''
        dp = [0] * (num+1)
        for i in range(1,num+1):
            if (i%2 == 1):# 奇数
                dp[i] = dp[i-1]+1
            else:# 偶数
                dp[i] = dp[i//2]
        return dp

416.分割等和子集

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

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

题解：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        '''
        本题本质是0-1背包问题
        状态定义dp[i][j] 表示在前i个物品可以装满容量j的背包
        如果不装物品i，则看i-1是否装满j
        如果装物品i，则i-1应该装满j-nums[i]
        dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
        target = sum(nums)
        if target % 2 == 1 return False,如果是奇数肯定不行
        target = target//2，这就是要满足的j
        初始化二维数组,行为每一个物品，列为背包的容量+1
        dp[0][0] = true
        遍历物品i，[1,n)
            遍历所有容量j,[0,target+1]
                如果j>=nums[i],容量大于当前物品重量，
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
                否则dp[i][j] = dp[i-1][j]，因为当前物品装不下
        最后返回dp[n-1][target]
        '''
        n = len(nums)
        target = sum(nums)
        if target % 2 != 0:
            return False
        target = target // 2
        dp = [[False]*(target+1) for i in range(n)]
        dp[0][0] = True
        for i in range(1,target+1):
            if(nums[0] == i):
                dp[0][i] = True
                break
        for i in range(1,n):
            for j in range(target+1):
                if j >= nums[I]:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

494.目标和

题目描述：
- 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
  返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-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
一共有5种方法让最终目标和为3。

题解

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        '''
        转换为0-1背包问题
        给定一些数字，使他们加减等于target
        可以将问题转化为：
            找到nums的一个正子集和一个负子集，使总和等于target，统计可能性的总数
        假设P为正子集，N为负子集。问题转换：
            sum(P) - sum(N) = target
            (两边同时加上sum(P)+sum(N),因为sum(P)+sum(N)=sum(nums))
            2 * sum(P) = target + sum(nums)
            sum(P) = (target+sum(nums)) / 2
        如果target+sum(nums)不是偶数，就不存在答案
        转换成0-1背包问题为：组合成容量为sum(P)的方式有多少种
        方法：
            dp的长度为P+1
            dp的第x项表示组成数字x有多少种方法，返回dp[P]
            更新dp数组：
                遍历nums，遍历的数记为num
                    逆序遍历从P到num，遍历的数记为j
                        dp[j] = dp[j-num] + dp[j]
        '''
        if sum(nums) < S or (sum(nums) + S) % 2 == 1: return 0
        P = (sum(nums) + S) // 2
        dp = [1] + [0 for _ in range(P)]
        for num in nums:
            for j in range(P,num-1,-1):
                dp[j] = dp[j - num] + dp[j]
        return dp[P]

647.回文子串

题目描述：
- 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例：

image.png
题解

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 在长度为N的字符串中，可能的回文中心位置有2N-1个：字母或者两个字母中间
        l = len(s)
        if l == 0:
            return 0
        count = 0
        # 以字母为中心的奇数长度回文串情况
        for center in range(l):
            left = right = center
            while left >= 0 and right < l and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        # 以某对元素为中心的偶数长度的回文串的情况
        for left in range(l-1):
            right = left + 1
            while left >= 0 and right < l and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        return count