leetcode - 動態(tài)規(guī)劃 - Part4

377. 組合總和 Ⅳ

題目描述

給定一個由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組憔四，找出和為給定目標正整數(shù)的組合的個數(shù)。 

示例: 
nums = [1, 2, 3]
target = 4
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

請注意，順序不同的序列被視作不同的組合。
因此輸出為 7。

進階： 
如果給定的數(shù)組中含有負數(shù)會怎么樣褥傍？ 
問題會產(chǎn)生什么變化？ 
我們需要在題目中添加什么限制來允許負數(shù)的出現(xiàn)喇聊？ 

Related Topics 動態(tài)規(guī)劃

題目分析：
由于數(shù)組中的數(shù)字可以重復(fù)使用摔桦，即每次的面臨的選擇為 $nums$ ，假如本次選擇的數(shù)字為 $nums[i]$ 承疲，則下次的目標成為 $target - nums[i]$ 。采用回溯算法：

class Solution:
    def __init__(self):
        self.res = 0

    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target == 0:
            self.res += 1
            return
        if target < 0:
            return
        for num in nums:
            self.combinationSum4(nums, target-num)
        return self.res

考慮重復(fù)計算問題鸥咖，使用備忘錄：

class Solution:
    def __init__(self):
        self.memory = {}

    def combinationSum4(self, nums: List[int], target: int) -> int:
        return self.combinationSum4Core(nums, target)
        
    def combinationSum4Core(self, nums, target):
        if target == 0:
            return 1
        if target < 0:
            return 0
        if target in self.memory:
            return self.memory[target]
        res = 0
        for num in nums:
            res += self.combinationSum4(nums, target-num)
        self.memory[target] = res
        return res

回溯算法采用自頂向下的計算燕鸽，既然有自頂向下的方案，那我們考慮自底向上的方法啼辣，也即動態(tài)規(guī)劃啊研。
由于每次選擇面臨的選擇都是整個數(shù)組，所以我們的狀態(tài)即為目標值鸥拧。所以定義狀態(tài) $dp[i]$ 表示目標和為 $i$ 的組合數(shù)党远。則狀態(tài)轉(zhuǎn)移方程為 $dp[i] = sum([dp[i-num] for num in nums if i >= num])$ .

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # dp[i] 表示和為i的組合數(shù)
        # dp[i] = sum([dp[i-num] for num in nums if i-num>=0])
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1, target+1):
            dp[i] = sum([dp[i-num] for num in nums if i-num>=0])
        # print(dp)
        return dp[target]

139. 單詞拆分

題目描述

給定一個非空字符串 s 和一個包含非空單詞的列表 wordDict，
判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞富弦。 

說明： 
拆分時可以重復(fù)使用字典中的單詞沟娱。 
你可以假設(shè)字典中沒有重復(fù)的單詞。 

示例 1： 
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"腕柜。
 
示例 2： 
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"济似。
 注意你可以重復(fù)使用字典中的單詞。
 
示例 3： 
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
Related Topics 動態(tài)規(guī)劃

題目分析
此題和上一題 [377] 很像盏缤，只是這里我們的目標變成了字符串砰蠢，每次面臨的選擇依然是整個字典“ν回溯即備忘錄方法一致台舱，動態(tài)規(guī)劃方法稍微有點差異，我們這里狀態(tài)定義為 $dp[i]$ 表示前 $i$ 個字符是否能被字典拆分潭流。這樣狀態(tài)轉(zhuǎn)移方程為 dp[i] = dp[i] or dp[i-len(word)] if i >= len(word) and s[i-len(word): i] == word竞惋。

1143. 最長公共子序列

題目描述

給定兩個字符串 text1 和 text2柜去，返回這兩個字符串的最長公共子序列的長度。 
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符
的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串碰声。 
例如诡蜓，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列胰挑。
兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列蔓罚。
若這兩個字符串沒有公共子序列，則返回 0瞻颂。 

示例 1: 
輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長公共子序列是 "ace"豺谈，它的長度為 3。
 
示例 2: 
輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc"贡这，它的長度為 3茬末。
 
示例 3: 
輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個字符串沒有公共子序列，返回 0盖矫。

提示: 
1 <= text1.length <= 1000 
1 <= text2.length <= 1000 
輸入的字符串只含有小寫英文字符丽惭。 
Related Topics 動態(tài)規(guī)劃

題目分析
本題是典型的二維動態(tài)規(guī)劃問題。對于字符 $s$ 辈双，若 $s$ 在公共字符串中责掏，則其同時在 $text1$ 和 $text2$ 中；若不在公共字符串中湃望，則要么在 $text1$ 中换衬，要么在 $text2$ 中。即 $s$ 在與不在 就為我們的選擇证芭。
直接看代碼也更方便理解：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # print(dp)
        return dp[m][n]

其中瞳浦，狀態(tài)各多設(shè)1個，省略初始化步驟废士。
主要疑問點是在 $dp[i][j-1], dp[i-1][j], dp[i-1][j-1]$ 中是否存在 $dp[i-1][j-1]$ 更大的情況叫潦，實際上通過下圖可以看出來， $dp[i-1][j-1]$ 不會比 $dp[i][j-1], dp[i-1][j]$ 更大湃密。

另外一個需要注意的是循環(huán)的順序诅挑，

dp[i][j]

計算需要依賴于

dp[i][j-1], dp[i-1][j], dp[i-1][j-1]

。

300. 最長上升子序列

題目描述

給定一個無序的整數(shù)數(shù)組泛源，找到其中最長上升子序列的長度拔妥。 

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

說明: 
可能會有多種最長上升子序列的組合没龙，你只需要輸出對應(yīng)的長度即可。 
你算法的時間復(fù)雜度應(yīng)該為 O(n2) 。 

進階: 
你能將算法的時間復(fù)雜度降低到 O(n log n) 嗎? 
Related Topics 二分查找 動態(tài)規(guī)劃

題目分析
對于這類序列長度問題硬纤，首先想到動態(tài)規(guī)劃方法求解解滓，其中狀態(tài)為數(shù)組中的數(shù)字，選擇為該數(shù)字能否添加進上升子序列筝家。我們定義狀態(tài)為 $dp[i]$ 表示以 $nums[i]$ 結(jié)尾的前綴序列能構(gòu)成的最長上升子序列長度洼裤。則狀態(tài)轉(zhuǎn)移方程為 dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n
        for i in range(1, n):
            dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1
        # print(dp)
        return max(dp)

我們再看一下進階的問題溪王，要求算法復(fù)雜度為 $O(n\,log\,n)$ 腮鞍，則算法中可能用到二分查找類算法。我們維護一個數(shù)組 $tail$ 莹菱， $tail[i]$ 表示長度為 $i+1$ 的上升子序列的結(jié)尾數(shù)字移国。對于當前數(shù)字，如果其大于 $tail[-1]$ 道伟，則我們將其添加到 $tail$ 末尾迹缀，若其小于 $tail[-1]$ ，則需要在 $tail$ 中找到第一個大于等于 $nums[i]$ 的數(shù)字蜜徽，將其替換為當前數(shù)字祝懂。
需要注意的是，為什么這樣做可以得到正確答案拘鞋？
因為我們的 $tail[i]$ 表示長度為 $i+1$ 的上升子序列的結(jié)尾數(shù)字嫂易，這個定義非常關(guān)鍵。假如我們的數(shù)組為 [2, 5, 3, 7, 101, 4]掐禁，最后我們的 $tail$ 數(shù)組為 [2, 3, 4, 101]，疑問點可能就出在 $tail[2]$ 上颅和，這個數(shù)字 $4$ 是我們原數(shù)組的最后一個數(shù)字傅事，現(xiàn)在它在 $tail$ 的中間位置，看似這樣形成的上升子序列不合理峡扩，但是其不影響最后長度的結(jié)果蹭越。假如我們考慮長度為 $3$ 的上升子序列，則以數(shù)字 $4$ 結(jié)尾的上升子序列結(jié)尾數(shù)字最小教届，在這種情形下响鹃，它才能在后面接更多的數(shù)字以形成更長的上升子序列。所以結(jié)果是正確的案训。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        tail = [nums[0]]
        for i in range(1, n):
            if nums[i] > tail[-1]:
                tail.append(nums[i])
            else:
                # 在tail里找到第一個大于等于nums[i] 的數(shù)字买置，進行替換
                low, high = 0, len(tail)-1
                while low < high:
                    mid = (low+high)//2
                    if tail[mid] < nums[i]:
                        low = mid + 1
                    else:
                        high = mid
                tail[high] = nums[i]
        # print(tail)
        return len(tail)

376. 擺動序列

題目描述

如果連續(xù)數(shù)字之間的差嚴格地在正數(shù)和負數(shù)之間交替，則數(shù)字序列稱為擺動序列强霎。
第一個差（如果存在的話）可能是正數(shù)或負數(shù)忿项。少于兩個元素的序列也是擺動序列。 

例如， [1,7,4,9,2,5] 是一個擺動序列轩触，因為差值 (6,-3,5,-7,3) 是正負交替出現(xiàn)的寞酿。
相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值
都是正數(shù)脱柱，第二個序列是因為它的最后一個差值為零伐弹。 

給定一個整數(shù)序列，返回作為擺動序列的最長子序列的長度榨为。 通過從原始序列中
刪除一些（也可以不刪除）元素來獲得子序列惨好，剩下的元素保持其原始順序。 

示例 1: 
輸入: [1,7,4,9,2,5]
輸出: 6 
解釋: 整個序列均為擺動序列柠逞。
 
示例 2: 
輸入: [1,17,5,10,13,15,10,5,16,8]
輸出: 7
解釋: 這個序列包含幾個長度為 7 擺動序列昧狮，其中一個可為[1,17,10,13,10,16,8]。 

示例 3: 
輸入: [1,2,3,4,5,6,7,8,9]
輸出: 2 

進階: 
你能否用 O(n) 時間復(fù)雜度完成此題? 
Related Topics 貪心算法 動態(tài)規(guī)劃

題目分析
和上一題 [300] 類似板壮，本題也是求子序列長度逗鸣，所以我們可以將狀態(tài)定義為以 $nums[i]$ 結(jié)尾的前綴子序列 XX 最大長度。因為序列為擺動序列绰精，大小交替撒璧，我們能否利用一個 $dp$ 數(shù)組來實現(xiàn)呢？上一題中笨使，我們的狀態(tài)轉(zhuǎn)移方程為 dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1卿樱。本題中我們要實現(xiàn)的是對交替數(shù)字的判斷，即 $nums[i]$ 究竟是大于還是小于 $nums[j]$ 依賴于以 $nums[j]$ 結(jié)尾的子序列最后是上升還是下降硫椰。如果只利用單個 $dp$ 數(shù)組繁调，我們無法記錄 $nums[j]$ 結(jié)尾的數(shù)組是上升還是下降的，于是考慮使用兩個數(shù)組來進行記錄靶草。直接看代碼：

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        up = [1] * n
        down  = [1] * n
        for i in range(1, n):
            up[i] = max([down[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1
            down[i] = max([up[j] if nums[i] < nums[j] else 0 for j in range(i)]) + 1
        # print(up)
        # print(down)
        return max(up+down)

其中 $up[i]$ 是記錄以 $nums[i]$ 結(jié)尾是上升的子序列長度蹄胰， $down[i]$ 是記錄以 $nums[i]$ 結(jié)尾是下降的子序列長度。此時的時間復(fù)雜度為 $O(n^2)$ 奕翔。
關(guān)注進階問題裕寨，需要用 $O(n)$ 的時間復(fù)雜度來解決問題。
我們同樣利用兩個數(shù)組派继，分別記錄前 $i$ 個元素可以組成的上升和下降子序列長度宾袜。

針對元素 $nums[i]$ ，有以下3中情況

$nums[i] > nums[i-1]$ 驾窟，此時 $up[i] = down[i-1] + 1$

若 $down[i-1]$ 恰好以 $nums[i-1]$ 結(jié)尾庆猫，則 $up[i] = down[i-1] + 1$ 。
若 $down[i-1]$ 的結(jié)尾數(shù)字為 $nums[j]$ 且 $j < i-1$ 绅络，則 $nums[j:i]$ 都為遞增序列阅悍，所以 $down[i-1]$ 一直等于 $down[j]$ 好渠，此時也滿足 $up[i] = down[i-1] + 1$ 。

$nums[i] < nums[i-1]$ 节视，此時 $down[i] = up[i-1] + 1$
$nums[i] = nums[i-1]$ 拳锚，保持不變

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        up = [1] * n
        down  = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1]
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]
        return max(up[n-1], down[n-1])

由于 $up$ 和 $down$ 都是依賴前一次的值，所以這里還可以進行空間度復(fù)雜度的優(yōu)化寻行。

174. 地下城游戲

題目描述

一些惡魔抓住了公主（P）并將她關(guān)在了地下城的右下角霍掺。地下城是由 M x N 個房間組成的二維網(wǎng)格。
我們英勇的騎士（K）最初被安置在左上角的房間里拌蜘，他必須穿過地下城并通過對抗惡魔來拯救公主杆烁。 

騎士的初始健康點數(shù)為一個正整數(shù)。如果他的健康點數(shù)在某一時刻降至 0 或以下简卧，他會立即死亡兔魂。 
有些房間由惡魔守衛(wèi)，因此騎士在進入這些房間時會失去健康點數(shù)（若房間里的值為負整數(shù)举娩，則表
示騎士將損失健康點數(shù)）析校；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點數(shù)
的魔法球（若房間里的值為正整數(shù)铜涉，則表示騎士將增加健康點數(shù)）智玻。 

為了盡快到達公主，騎士決定每次只向右或向下移動一步芙代。 

編寫一個函數(shù)來計算確保騎士能夠拯救到公主所需的最低初始健康點數(shù)吊奢。 

例如，考慮到如下布局的地下城纹烹，如果騎士遵循最佳路徑 右 -> 右 -> 下 -> 下页滚，則騎士的初始健康點數(shù)至少為 7。 

-2 (K)  -5     10
-3      -10    30
 3       1    -5(P)

說明: 
騎士的健康點數(shù)沒有上限铺呵。 
任何房間都可能對騎士的健康點數(shù)造成威脅逻谦，也可能增加騎士的健康點數(shù)，包括騎士進入的左上角房間以及公主被監(jiān)禁的右下角房間陪蜻。 
Related Topics 二分查找 動態(tài)規(guī)劃

題目分析
面對這種網(wǎng)格路徑問題，首先想到利用二維動態(tài)規(guī)劃進行求解贱鼻。我們按照常規(guī)思路設(shè)定狀態(tài)為騎士走到位置 $(i, j)$ 所需要的的最少初始健康點數(shù)宴卖。假如是求路徑和，則我們的狀態(tài)轉(zhuǎn)移方程為 $dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + dungeon[i][j]$ 邻悬，由于本題中是需要求得初始健康點數(shù)症昏，那我們是不是可以將狀態(tài)轉(zhuǎn)移方程寫成 $dp[i][j] = max(1, min(dp[i-1][j], dp[i][j-1]) +dungeon[i][j])$ 呢？答案是否定的父丰。這是因為題目中要求我們求得走到右下角所需最小健康點數(shù)肝谭，不管當前是在什么位置掘宪，我們的目標都是 $(m-1, n-1)$ ，所以 $dp[i][j]$ 依賴的不是 $dp[i-1][j],dp[i][j-1]$ 攘烛，而是依賴于 $dp[i+1][j],dp[i][j+1]$ 魏滚，同時我們的狀態(tài)需要定義為騎士從位置 $(i, j)$ 走到右下角所需的初始健康點數(shù)，否則 $dp[i][j]$ 不滿足無后效性的要求坟漱。
有了狀態(tài)轉(zhuǎn)移方程鼠次，接下來需要確認 $base case$ ，按照題目要求芋齿，騎士最低健康點數(shù)必須大于0腥寇，當?shù)竭_位置 $(m-1, n-1)$ 時，其依賴于 $dp[m][n-1],dp[m-1][n]$ 觅捆，而在位置 $(m, n-1)$ 和 $(m-1, n)$ 時赦役，騎士的最小健康點數(shù)為1。

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # dp[i][j] 表示從位置 (i, j) 達到右下角所需的最低健康點數(shù)
        m, n = len(dungeon), len(dungeon[0])
        if m == 0 or n == 0:
            return 1
        dp = [[float('inf')] * (n+1) for _ in range(m+1)]
        dp[m-1][n] = dp[m][n-1] = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
        # print(dp)
        return dp[0][0]

53. 最大子序和

題目描述

給定一個整數(shù)數(shù)組 nums 栅炒，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）掂摔，返回其最大和。 

示例: 
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大职辅，為 6棒呛。
 
進階: 
如果你已經(jīng)實現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解域携。 
Related Topics 數(shù)組 分治算法 動態(tài)規(guī)劃

題目分析
對于這類子數(shù)組的問題簇秒，狀態(tài)定義一般為以 $nums[i]$ 結(jié)尾的子數(shù)組XX。由此秀鞭，本題 $dp[i]$ 即可定義為以 $nums[i]$ 結(jié)尾的子數(shù)組的最大和趋观。如果 $nums[i]$ 能夠加在 $nums[i-1]$ 后形成更大的和，則 dp[i] = dp[i-1]+nums[i]锋边，否則皱坛， $nums[i]$ 單獨形成一個更大的和，即 dp[i] = nums[i]豆巨。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp[i] 表示nums[i]結(jié)尾的子數(shù)組的最大和
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i-1]+nums[i])
        # print(dp)
        return max(dp)

131. 分割回文串

題目描述

給定一個字符串 s剩辟，將 s 分割成一些子串，使每個子串都是回文串往扔。 
返回 s 所有可能的分割方案贩猎。 

示例: 
輸入: "aab"
輸出:
[
  ["aa","b"],
  ["a","a","b"]
] 
Related Topics 回溯算法

題目分析
由于最后輸出的結(jié)果為分割的具體方案，因此需要使用回溯算法萍膛。對于每個拆分結(jié)果的判斷吭服，我們可以嘗試使用動態(tài)規(guī)劃進行數(shù)據(jù)預(yù)處理。其中 $dp[i][j]$ 表示 $s[i: j+1]$ 是否為回文字符串蝗罗。所以狀態(tài)轉(zhuǎn)移方程為 dp[i][j] = dp[i+1][j-1] and s[i]==s[j]艇棕。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 動態(tài)規(guī)劃預(yù)處理數(shù)據(jù)
        # dp[i][j] 表示 s[i:j+1] 是否為回文串
        dp = [[False] * n for _ in range(n)]
        # 初始化
        for i in range(n):
            dp[i][i] = True
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if j - i > 1:
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j]
        # print(dp)
        # 取得結(jié)果
        res = []
        self.getResult(s, len(s), 0, dp, [], res)
        return res
    
    def getResult(self, s, n, start, dp, path, res):
        if start == n:
            res.append(path[:])
            return
        for i in range(start, n):
            if not dp[start][i]:
                continue
            path.append(s[start: i+1])
            self.getResult(s, n, i+1, dp, path, res)
            path.pop()

132. 分割回文串 II

題目描述

給定一個字符串 s蝌戒，將 s 分割成一些子串，使每個子串都是回文串沼琉。 
返回符合要求的最少分割次數(shù)北苟。 

示例: 
輸入: "aab"
輸出: 1
解釋: 進行一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串。

Related Topics 動態(tài)規(guī)劃

題目分析
最簡單的方案莫過于采用【131】題的解法刺桃，最后計算最短的分割方案即可得出結(jié)果粹淋。但是這種方法復(fù)雜度高，且由于不需要返回最終結(jié)果瑟慈，對于這類最小次數(shù)問題桃移，嘗試采用動態(tài)規(guī)劃進行求解。假如定義 $dp[i]$ 為子字符串 $s[0: i+1]$ 分割成回文串的最小分割次數(shù)葛碧，那我們的狀態(tài)轉(zhuǎn)移方程又該怎么寫呢借杰？對于子字符串 $s[0: i+1]$ ，候選分割方案為 $1...i$ 的任意位置进泼，假如分割位置為 $j$ 蔗衡，需要滿足什么條件呢？由于 $dp[j]$ 為子字符串 $s[0:j+1]$ 分割成回文子串的最少分割次數(shù)乳绕，如果 $s[j+1: i+1]$ 也為回文串绞惦，那我們就找到了一個結(jié)果—— $dp[j]+1$ 。我們遍歷 $1...i$ 的任意位置洋措，然后求取最小值即為我們的結(jié)果济蝉。

class Solution:
    def minCut(self, s: str) -> int:
        # dp[i] 表示將子字符串 s[0: i+1] 分割成回文字符串的最少分割次數(shù)
        # dp[i] = min([dp[j]+1 if s[j+1:i+1] 是回文串 else n for j in range(i)])
        n = len(s)
        dp = [n] * n
        dp[0] = 0
        for i in range(1, n):
            if self.isPalindrome(s, 0, i):
                dp[i] = 0
                continue
            dp[i] = min([dp[j]+1 if self.isPalindrome(s, j+1, i) else n for j in range(i)])
        # print(dp)
        return dp[n-1]

    def isPalindrome(self, s, start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

其中判斷回文串還能采用記憶化的方式，以避免重復(fù)計算菠发。又聯(lián)想到【131】中的數(shù)據(jù)預(yù)處理方案王滤，本題中我們依然可以采用。

115. 不同的子序列

題目描述

給定一個字符串 S 和一個字符串 T滓鸠，計算在 S 的子序列中 T 出現(xiàn)的個數(shù)雁乡。 
一個字符串的一個子序列是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串糜俗。
（例如踱稍，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是） 

題目數(shù)據(jù)保證答案符合 32 位帶符號整數(shù)范圍悠抹。 

示例 1： 
輸入：S = "rabbbit", T = "rabbit"
輸出：3
解釋：
如下圖所示, 有 3 種可以從 S 中得到 "rabbit" 的方案珠月。
(上箭頭符號 ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
 
示例 2： 
輸入：S = "babgbag", T = "bag"
輸出：5
解釋：
如下圖所示, 有 5 種可以從 S 中得到 "bag" 的方案。 
(上箭頭符號 ^ 表示選取的字母)
babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^ 
Related Topics 字符串 動態(tài)規(guī)劃

題目分析
本題可以看著兩個字符串的匹配問題锌钮。所以對于 $s[i]$ 和 $t[j]$ 的匹配有兩種情況：要么匹配，要么不匹配引矩。根據(jù)題目要求梁丘，對于匹配的情況侵浸，我們可以選擇該字符，若不匹配氛谜，我們只能不選擇該字符掏觉。

class Solution:
    def __init__(self):
        self.res = 0

    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        self.numDistinctCore(s, t, n, 0, m, 0)
        return self.res

    def numDistinctCore(self, s, t, n, i, m, j):
        if m == j:
            self.res += 1
            return
        if i >= n:
            return
        # 選擇該字符
        if s[i] == t[j]:
            self.numDistinctCore(s, t, n, i+1, m, j+1)
        # 不選擇該字符
        self.numDistinctCore(s, t, n, i+1, m, j)

有了回溯解法，那動態(tài)規(guī)劃就相對簡單了值漫。定義 $dp[i][j]$ 表示 $t[:j]$ 在 $s[:i]$ 的子序列中出現(xiàn)次數(shù)澳腹。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if m < n:
            return 0
        # dp[i][j] 表示s[:i] 的子串中 t[:j] 出現(xiàn)的次數(shù)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = 1
        for i in range(1, m+1):
            for j in range(1, min(n, i)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        # print(dp)
        return dp[m][n]

參考

https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/