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

• 動態(tài)規(guī)劃問題：
  1. 定義狀態(tài)：
     即定義數(shù)據(jù)元素的含義
  2. 建立狀態(tài)轉(zhuǎn)移方程：
  3. 設(shè)定初始值：
  4. 狀態(tài)壓縮：
     即優(yōu)化數(shù)組空間，每次狀態(tài)的更新只依賴于前一次的狀態(tài)，優(yōu)化一般作用于多維數(shù)組，
     觀察是否可以將多維數(shù)組以一維數(shù)組來動態(tài)表示，即用一維數(shù)組來保存上次的狀態(tài)。
  5. 選出結(jié)果(返回值)

5.最長回文子串

• 題目描述：
  • 給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。
• 示例：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
輸入: "cbbd"
輸出: "bb"

• python二維數(shù)組的創(chuàng)建

#[[0]*3]*3的方式是不可行的，淺拷貝的數(shù)組指向同一個(gè)內(nèi)存
list_three = [[0]*3]*3
print(list_three) #結(jié)果為[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:
        '''
        如果字符串的首尾兩個(gè)字符不相等，那么不是回文
        如果首尾字符相等，再判斷里面的子串，縮小規(guī)模，判斷整體是否是回文
        i,j為要判斷的某段字符串的左右下標(biāo)
        dp[i][j] => s[i]-s[j]
        dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
        i和j的關(guān)系應(yīng)該是i<=j
        dp[i+1][j-1]的邊界條件是[i+1,j-1]不構(gòu)成區(qū)間，即長度小于2
        即j - 1 - (i + 1) +1 < 2,也就是j - i < 3 (下標(biāo)關(guān)系)
        所以i到j(luò)的長度要滿足j - i + 1 < 4 
        所以當(dāng)子串的長度等于2或者等于3的時(shí)候，只要判斷首尾的字符是否相等即可
        所以如果同時(shí)滿足s[i] == s[j] 和 j - i < 3的前提下，
            dp[i][j] = true
        可以肯定的有dp[i][i] = true
        只要得到dp[i][j] = true就記錄子串的長度和起始位置
        '''
        size = len(s)
        #如果只有一個(gè)肯定是回文
        if size < 2:
            return s
        #創(chuàng)建一個(gè)二維數(shù)組
        dp = [[False for i in range(size)] for j in range(size)]
        #初始一個(gè)默認(rèn)值
        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]:
                    #如果同時(shí)滿足，則為true
                    if j - i < 3:
                        dp[i][j] = True
                    #如果只滿足s[i]=s[j]則縮小規(guī)模
                    else:
                        #j是終止位置，所以某個(gè)字符串到j(luò)-1是否為回文肯定已經(jīng)判斷過了
                        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#長度
                    #如果當(dāng)前回文長度比已保存的最大長度更長，則更新值保存長度以及起始位置
                    if cur_len > max_len:
                        max_len = cur_len
                        start = I
        #起點(diǎn)下標(biāo)為start，終點(diǎn)下標(biāo)為start+長度-1，所以截取[start:start+max_len]
        return s[start:start+max_len]

62.不同路徑

• 題目描述：
  • 一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角
    機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角
    問總共有多少條不同的路徑？
• 示例：

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
(1) 向右 -> 向右 -> 向下
(2)向右 -> 向下 -> 向右
(3) 向下 -> 向右 -> 向右

• 題解：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        '''
        dp[i][j]: i表示列，j表示行
        機(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.最小路徑和

• 題目描述：
  • 給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
    說明：每次只能向下或者向右移動一步。
• 示例：

輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?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矩陣，因?yàn)楸闅v過的元素不會再用到了
        所以沒必要新建一個(gè)dp矩陣?yán)速M(fèi)空間
        '''
        for i in range(len(grid)):#grip的長度，也就是行
            for j in range(len(grid[0])):#列
                if i == j == 0: 
                    #覆蓋到原矩陣上，又因?yàn)間rid[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.不同的二叉搜索樹

• 題目描述：
  • 給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？
• 示例：

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:

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

• 題解：

class Solution:
    def numTrees(self, n: int) -> int:
        '''
        假設(shè)f(n) = 有n個(gè)數(shù)字可以構(gòu)建幾種搜索樹
        f(0) = 1 理解為沒有數(shù)字就只有為空的一種情況
        f(1) = 1
        f(2) = 2
        當(dāng)n=3時(shí)：
        (1)如果1為樹根，左邊有f(0)種情況，右邊f(xié)(2)種情況，一共有f(0)*f(2)
        (2)如果2為樹根，左邊有f(1),右邊f(xié)(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)
        每一項(xiàng)兩個(gè)f()中的數(shù)字加起來都等于n-1
        根據(jù)已知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  #兩個(gè)f()中的數(shù)字之和等于m-1
            count = 0
            for i in range(m):
                count += nums[i]*nums[s-i]
            nums.append(count)
        return nums[n]

139.單詞拆分

• 題目描述：
  • 給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。
    說明：
    拆分時(shí)可以重復(fù)使用字典中的單詞。
    你可以假設(shè)字典中沒有重復(fù)的單詞。
• 示例

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"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為開始下標(biāo)
            for j in range(i+1,n+1):#j為結(jié)束下標(biāo)
                #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.乘積最大子數(shù)組

• 題目描述
  • 給你一個(gè)整數(shù)數(shù)組 nums ，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積。
• 示例

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [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]
        # 結(jié)果變量初始化
        res = nums[0]  
        #初始化當(dāng)前的最大值、最小值
        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
            # 因?yàn)楫?dāng)前nums[i]可正可負(fù)，所以得到的left，right大小關(guān)系不確定
            pre_max = max(left, right, nums[I])
            pre_min = min(left, right, nums[I])
            #保存結(jié)果變量
            res = max(res, pre_max)
        return res

221.最大正方形

• 題目描述：
  • 在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形，并返回其面積。
• 示例：

輸入: 

  1 0 1 0 0
  1 0 1 1 1
  1 1 1 1 1
  1 0 0 1 0

輸出: 4

• 題解

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        '''
        dp[i][j] 表示以matrix[i][j]為右下角的頂點(diǎn)的可以組成的最大正方形的邊長
        if matrix[i][j] == 0: return 0
        if matrix[i][j] == 1: 將martix[i][j]往左和往上延伸
        要取另外三個(gè)點(diǎn)的最小值然后+1，只有最小值才是能與[i][j]一起構(gòu)成新正方形的
        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
        # 不知道為何，這兩句放到前面就報(bào)錯(cuò)，無解，測試用例能過，提交就報(bào)錯(cuò)
        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):
                # 如果當(dāng)前值為1，則判斷當(dāng)前位置所能組成的最大正方形邊長，
                # 如果當(dāng)前值不為1，則租不成正方形不去判斷，二維數(shù)組默認(rèn)值都為0
                if matrix[i][j] == '1':
                    # 如果i或者j為0，則在邊上，最大邊長只能為1
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:# 不在邊上則計(jì)算其最大邊長
                        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.完全平方數(shù)

• 題目描述：
  • 給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。
• 示例：

輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.

• 題解：

class Solution:
    def numSquares(self, n: int) -> int:
        '''
        dp[i]表示最少可以由幾個(gè)平方數(shù)構(gòu)成
        初始化dp=[0,1,2,...,n],長度為n+1，最多次數(shù)就是全部由1構(gòu)成
        遍歷dp，對于i，遍歷區(qū)間[2,n+1)即2 -> n
        遍歷所有平方數(shù)小于i的數(shù)j，遍歷區(qū)間[1,int(√i)+1） 即1 -> int(√i)
            dp[i] = min(dp[i],dp[i-j*j]+1),始終保存所有可能情況的最小值
            dp[i-j*j]+1就跟找零問題類似，減去所有小的平方數(shù)，找到剩下的數(shù)所需的最小值
        '''
        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.最長上升子序列

• 題目描述：
  • 給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
• 示例

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

• 題解

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        '''
        子序列并不要求連續(xù)!!!!
        dp[i]表示nums前i個(gè)數(shù)字的最長子序列長度
        當(dāng)0<=j<i，每輪計(jì)算dp[i]時(shí)，遍歷[0,i)區(qū)間：
            nums[i]>nums[j]時(shí)，子序列長度為dp[j]+1
            nums[i]<=nums[j]時(shí)，上升子序列不成立
        dp[i] = max(dp[j]+1,dp[i])
        
        '''
        if not nums:
            return 0
        # 初始狀態(tài)都為1，每個(gè)數(shù)字都可以單獨(dú)作為一個(gè)子序列
        dp = [1] * len(nums)
        for i in range(1,len(nums)):
            for j in range(i):
                #因?yàn)橐髧?yán)格遞增，所以不能小于等于
                #nums[i]>nums[j]，則nums[i]可以接到nums[j]后邊
                #其長度為以nums[j]結(jié)尾的子序列長度+1
                if nums[j] < nums[I]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

309.最佳買賣股票時(shí)期含冷凍期

• 題目描述：
  • 給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 。?
    設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
    你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
    賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

• 示例

輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

• 題解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''
        取n = len(prices)，以[0,0]對n進(jìn)行循環(huán)得到二維數(shù)組
        dp[i][j]: i代表天數(shù)，j代表是否持股(0，1)
        dp[i][0]:第i-1天不持股或者第i-1天持股但是第i天賣出了
        dp[i][1]:因?yàn)橐欣鋬銎冢赃@里不是單純第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])
        # 分別計(jì)算每一天持股與不持股的最大利潤
        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])
        #返回最后一天不持股的利潤，因?yàn)樽詈笠惶觳怀止煽隙ū瘸止衫麧櫢?        return dp[-1][0]

322.零錢兌換

• 題目描述：
  • 給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -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:  # 枚舉硬幣種數(shù)
            for j in range(c, amount+1):  # 從小到大枚舉金額，確保j-c >= 0.
                f[j] = min(f[j], f[j - c] + 1)
        # 如果為inf說明狀態(tài)不可達(dá)，返回-1即可。
        return f[amount] if f[amount] != float('inf') else -1  

338.比特位計(jì)數(shù)

• 題目描述：

  • 給定一個(gè)非負(fù)整數(shù) num。對于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。

• 示例

  
  
  image.png

• 題解：

class Solution:
    def countBits(self, num: int) -> List[int]:
        '''
        二進(jìn)制的特性：
            奇數(shù)的二進(jìn)制中1的個(gè)數(shù) = 它上一位偶數(shù)的二進(jìn)制中1的個(gè)數(shù) + 1
            偶數(shù)的二進(jìn)制中1的個(gè)數(shù) = (這個(gè)偶數(shù) // 2)得到的數(shù)的二進(jìn)制中1的個(gè)數(shù)
        '''
        dp = [0] * (num+1)
        for i in range(1,num+1):
            if (i%2 == 1):# 奇數(shù)
                dp[i] = dp[i-1]+1
            else:# 偶數(shù)
                dp[i] = dp[i//2]
        return dp

416.分割等和子集

• 題目描述：
  • 給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
• 示例：

輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].

• 題解：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        '''
        本題本質(zhì)是0-1背包問題
        狀態(tài)定義dp[i][j] 表示在前i個(gè)物品可以裝滿容量j的背包
        如果不裝物品i，則看i-1是否裝滿j
        如果裝物品i，則i-1應(yīng)該裝滿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,如果是奇數(shù)肯定不行
        target = target//2，這就是要滿足的j
        初始化二維數(shù)組,行為每一個(gè)物品，列為背包的容量+1
        dp[0][0] = true
        遍歷物品i，[1,n)
            遍歷所有容量j,[0,target+1]
                如果j>=nums[i],容量大于當(dāng)前物品重量，
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
                否則dp[i][j] = dp[i-1][j]，因?yàn)楫?dāng)前物品裝不下
        最后返回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.目標(biāo)和

• 題目描述：
  • 給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)，S?，F(xiàn)在你有兩個(gè)符號 + 和 -。對于數(shù)組中的任意一個(gè)整數(shù)，你都可以從 + 或 -中選擇一個(gè)符號添加在前面。
    返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號的方法數(shù)。

• 示例：

輸入：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種方法讓最終目標(biāo)和為3。

• 題解

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        '''
        轉(zhuǎn)換為0-1背包問題
        給定一些數(shù)字，使他們加減等于target
        可以將問題轉(zhuǎn)化為：
            找到nums的一個(gè)正子集和一個(gè)負(fù)子集，使總和等于target，統(tǒng)計(jì)可能性的總數(shù)
        假設(shè)P為正子集，N為負(fù)子集。問題轉(zhuǎn)換：
            sum(P) - sum(N) = target
            (兩邊同時(shí)加上sum(P)+sum(N),因?yàn)閟um(P)+sum(N)=sum(nums))
            2 * sum(P) = target + sum(nums)
            sum(P) = (target+sum(nums)) / 2
        如果target+sum(nums)不是偶數(shù)，就不存在答案
        轉(zhuǎn)換成0-1背包問題為：組合成容量為sum(P)的方式有多少種
        方法：
            dp的長度為P+1
            dp的第x項(xiàng)表示組成數(shù)字x有多少種方法，返回dp[P]
            更新dp數(shù)組：
                遍歷nums，遍歷的數(shù)記為num
                    逆序遍歷從P到num，遍歷的數(shù)記為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.回文子串

• 題目描述：

  • 給定一個(gè)字符串，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串。
    具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會被計(jì)為是不同的子串。

• 示例：

  
  
  image.png

• 題解

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 在長度為N的字符串中，可能的回文中心位置有2N-1個(gè)：字母或者兩個(gè)字母中間
        l = len(s)
        if l == 0:
            return 0
        count = 0
        # 以字母為中心的奇數(shù)長度回文串情況
        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
        # 以某對元素為中心的偶數(shù)長度的回文串的情況
        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