一、坐標(biāo)型動態(tài)規(guī)劃

例1. Unique Paths II

題目描述：
給定m行n列的網(wǎng)格纹因，有一個(gè)機(jī)器人從左上角(0,0)出發(fā)喷屋，每一步可以向下或者向右走一步。網(wǎng)格中有些地方有障礙瞭恰，機(jī)器人不能通過障礙格逼蒙。問有多少種不同的方式走到右下角？（輸入二維數(shù)組，如果數(shù)組的元素為1是牢，表示該位置有障礙僵井；為0表示沒有障礙。）

解析： 這題和Unique Path非常類似驳棱，只是網(wǎng)格中可能有障礙批什。最后一步一定是從左邊(i, j-1)或上邊(i-1, j)過來。狀態(tài)f[i][j]表示從左上角有多少種方式走到格子(i, j) 社搅。坐標(biāo)型動態(tài)規(guī)劃：數(shù)組下標(biāo) [i][j] 即坐標(biāo)(i, j)驻债，f[i][j] = f[i-1][j] + f[i][j-1]。

f[i][j] = 機(jī)器人有多少種方式從左上角走到(i, j)：

• 如果左上角(0, 0)格或者右下角(m-1, n-1)格有障礙形葬，直接輸出0
• 如果(i, j)格有障礙合呐，f[i][j] = 0，表示機(jī)器人不能到達(dá)此格（0種方式）
• 初始條件：f[0][0] = 1
• 一般情況下：
  如果(i, j)格有障礙笙以，f[i][j] = 0
  如果j=1淌实，即第一列，f[i][j] = f[i-1][j]
  如果i=1猖腕，即第一行拆祈，f[i][j] = f[i][j-1]
  其他，f[i][j] = f[i-1][j] + f[i][j-1]

代碼如下：

def uniquePathsWithObstacles(obstacleGrid):
    states = obstacleGrid
    for i in range(len(states)):
        for j in range(len(states[i])):
            if i == 0 and j == 0:
                states[i][j] = 1 - states[i][j]
            elif i == 0:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i][j - 1]
            elif j == 0:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i - 1][j]
            else:
                if states[i][j] == 1:
                    states[i][j] = 0
                else:
                    states[i][j] = states[i - 1][j] + states[i][j - 1]
    if states[-1][-1] > 2147483647:
        return -1
    else:
        return states[-1][-1]

例2. Longest Increasing Continuous Subsequence

題目描述：
給定a[0], …, a[n-1]倘感，找到最長連續(xù)遞增子序列i, i+1, i+2, …, j, 使得a[i]<a[i+1]<…<a[j]放坏，輸出長度j-i+1。
例子：
輸入：[5, 1, 2, 3, 4]
輸出：4 (子序列1, 2, 3, 4)

設(shè)f[j] =以a[j]結(jié)尾的最長連續(xù)上升子序列的長度老玛，f[j] = max{ 1, f[j–1]+1| j>0 and a[j-1] < a[j]}淤年。情況1：子序列 就是a[j]本身；情況2：以a[j-1]結(jié)尾的最長連續(xù) 上升子序列的長度蜡豹，加上a[j]麸粮。

計(jì)算f[0], f[1], f[2], …, f[n-1]
? 和硬幣組合題不一樣的是，最終答案并不一定是f[n-1]
? 因?yàn)槲覀儾恢雷顑?yōu)策略中最后一個(gè)元素是哪個(gè)a[j]
? 所以答案是max{f[0], f[1], f[2], …, f[n-1]}
? 算法時(shí)間復(fù)雜度O(n)余素，空間復(fù)雜度O(n)

 def findLengthOfLCIS(nums):
        if len(nums) < 1:
            return 0
        states = [1]
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                states.append(states[i-1] + 1)
            else:
                states.append(1)
        return max(states)

例3. Minimum Path Sum

題目描述：
給定m行n列的網(wǎng)格豹休，每個(gè)格子(i, j)里都一個(gè)非負(fù)數(shù)A[i][j]。求一個(gè)從左上角(0, 0)到右下角的路徑桨吊，每一步只能向下或者向右走一步威根，使得路徑上的格子里的數(shù)字之和最小，輸出最小數(shù)字和视乐。

設(shè)從(0, 0)走到(i, j)的路徑最小數(shù)字總和f[i][j]洛搀，f[i][j] = min{f[i-1][j], f[i][j-1]} + A[i][j] ，初始條件：f[0][0] = A[0][0]佑淀；邊界情況：i = 0 或 j = 0留美，則前一步只能有一個(gè)方向過來。

? 計(jì)算第0行：f[0][0], f[0][1], …, f[0][n-1]
? 計(jì)算第1行：f[1][0], f[1][1], …, f[1][n-1]
? …
? 計(jì)算第m-1行：f[m-1][0], f[m-1][1], …, f[m-1][n-1]
? 時(shí)間復(fù)雜度（計(jì)算步數(shù)）：O(MN)，空間復(fù)雜度（數(shù)組大谢牙）：O(MN)

def minPathSum(grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if not i and not j:
                    continue
                if not i:
                    grid[i][j] += grid[i][j-1]
                elif not j:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += min(grid[i][j-1], grid[i-1][j])
        return grid[m-1][n-1]

這種方式是在原數(shù)組上直接修改逢倍，考慮到計(jì)算第 i 行時(shí)，只需要第 i 行和第 i-1 行的 f景图， 所以较雕，只需要保存兩行的f值：f[i][0..n-1]和f[i-1][0..n-1]，用滾動數(shù)組實(shí)現(xiàn)挚币。實(shí)際操作時(shí)用滾動法：
? 計(jì)算f[0][0],..,f[0][n-1], 計(jì)算f[1][0],..,f[1][n-1]
? 計(jì)算f[2][0..n-1]時(shí)亮蒋，把值寫在f[0][0..n-1]的數(shù)組里
? 同理，f[3][0..n-1]寫在f[1][0..n-1]的數(shù)組里
? 最后f[m-1][n-1]存儲在f[0][n-1]（或者f[1][n-1]）里妆毕，直接輸出瓤荔。

滾動數(shù)組代碼如下：

def minPathSum(grid: List[List[int]]) -> int:
        m = len(grid)  
        n = len(grid[0])
        states = [[0]*n]*2       
        for i in range(m):
            for j in range(n):
                if not i and not j:
                    states[i][j] = grid[i][j]
                elif not i:
                    states[i%2][j] = states[i%2][j-1] + grid[i][j]
                elif not j:
                    states[i%2][j] = states[(i+1)%2][j] + grid[i][j]
                else:
                    states[i%2][j] = min(states[i%2][j-1], states[(i+1)%2][j]) + grid[i][j]
        return states[(m-1)%2][n-1]
        

例4.Counting Bits

題目描述：
給定N守问，要求輸出0, 1, …, N的每個(gè)數(shù)的二進(jìn)制表示里的1的個(gè)數(shù)
例子：
輸入：5
輸出：[0, 1, 1, 2, 1, 2]
0：0
1：1
2：10
3：11
4：100
5：101

最后一步：觀察這個(gè)數(shù)最后一個(gè)二進(jìn)制位（最低位）狐树，去掉它符相，看剩下 多少個(gè)1
(170)10 = (10101010) 2
(85)10 = (1010101) 2
85的二進(jìn)制表示里有4個(gè)1
170的二進(jìn)制表示里有4個(gè)1

設(shè)f[i]表示i的二進(jìn)制表示中有多少個(gè)1哥童，f[i] = f[i>>1] + (i & 1)燃乍。初始條件：f[0] = 0香到，依次計(jì)算 f[0], f[1], f[2], …, f[N]
? 時(shí)間復(fù)雜度O(N)
? 空間復(fù)雜度O(N)

def countBits(num: int) -> List[int]:
        states = [0] * (num+1)
        states[0] = 0
        for i in range(1, num+1):
            states[i] = states[i >> 1] + (i&1)
        return states

小結(jié)

• 坐標(biāo)型動態(tài)規(guī)劃是最簡單的動態(tài)規(guī)劃類型图柏。
• 給定一個(gè)序列或網(wǎng)格序六，需要找到序列中某個(gè)/些子序列或網(wǎng)格中的某條路徑（某種性質(zhì)最大/最小、計(jì)數(shù)蚤吹、存在性）例诀。
• 動態(tài)規(guī)劃方程 f[i] 中的下標(biāo) i 表示以 ai 為結(jié)尾的滿足條件的子序列的性質(zhì)，f[i][j] 中的下標(biāo)i, j表示以格子(i, j)為結(jié)尾的滿足條件的路徑的性質(zhì)（ 最大值/最小值裁着、個(gè)數(shù)繁涂、是否存在）。
• 坐標(biāo)型動態(tài)規(guī)劃的初始條件f[0]就是指以a0為結(jié)尾的子序列的性質(zhì)
• 二維空間優(yōu)化：如果f[i][j]的值只依賴于當(dāng)前行和前一行二驰，則可以用滾動 數(shù)組節(jié)省空間

二扔罪、序列型動態(tài)規(guī)劃

給出一個(gè)序列：

• 動態(tài)規(guī)劃方程f[i]中的下標(biāo)i表示前i個(gè)元素a[0], a[1], ..., a[i-1]的某種性質(zhì)（坐標(biāo)型的f[i]表示以a i 為結(jié)尾的某種性質(zhì)）
• 初始化中,f[0]表示空序列的性質(zhì)（坐標(biāo)型動態(tài)規(guī)劃的初始條件f[0]就是指以a 0 為結(jié)尾的子序列的性質(zhì)）

2.1 序列+狀態(tài)型動態(tài)規(guī)劃

例1. Paint House

題目描述：
有一排N棟房子，每棟房子要漆成3種顏色中的一種：紅桶雀、藍(lán)矿酵、綠，任何兩棟相鄰的房子不能漆成同樣的顏色矗积。第 i 棟房子染成紅色全肮、藍(lán)色、綠色的花費(fèi)分別是cost[i][0], cost[i][1], cost[i][2]棘捣。問最少需要花多少錢油漆這些房子辜腺？
例子：
輸入： N=3 ; Cost = [[14,2,11],[11,14,5],[14,3,10]]
輸出：10 （第0棟房子藍(lán)色，第1棟房子綠色，第2棟房子藍(lán)色, 2+5+3=10）

第一步：確定狀態(tài)

最優(yōu)策略是花費(fèi)最小的策略评疗。

• 最后一步
  最優(yōu)策略中最后一棟房子N一定染成了紅测砂、藍(lán)、綠中的一種百匆。但是相鄰兩棟房子不能漆成一種顏色：如果最優(yōu)策略中房子N是紅色邑彪，房子N-1只能是藍(lán)色或綠色；如果最優(yōu)策略中房子N是藍(lán)色胧华，房子N-1只能是紅色或綠色寄症；如果最優(yōu)策略中房子N是綠色，房子N-1只能是紅色或藍(lán)色矩动。如果直接套用以前的思路有巧，記錄油漆N棟房子的最小花費(fèi)，根據(jù)套路悲没，也需要記錄油漆前N-1棟房子的最小花費(fèi)篮迎。但是，前N-1棟房子的最小花費(fèi)的最優(yōu)策略中示姿，又不知道第N-1棟房子是什么顏色甜橱，所以有可能和最后一棟房子N撞色。既然不知道房子N-1是什么顏色栈戳，就把它記錄下來——分別記錄油漆前N-1棟房子并且房子N-1是紅色岂傲、藍(lán)色、綠色的最小花費(fèi)子檀。

• 子問題
  求油漆前N棟房子并且最后一棟房子N是紅色镊掖、藍(lán)色、綠色的最小花費(fèi)褂痰，需要知道油漆前N-1棟房子并且房子N-1是紅色亩进、藍(lán)色、綠色的最小花費(fèi)缩歪。

• 狀態(tài)：設(shè)油漆前i棟房子并且第 i 棟房子是紅色归薛、藍(lán)色、綠色的最小花費(fèi)分別為 f[i][0], f[i][1], f[i][2]

第二步：轉(zhuǎn)移方程

設(shè)油漆前 i 棟房子并且第 i 棟房子是紅色匪蝙、藍(lán)色主籍、綠色的最小花費(fèi)分別為 f[i][0], f[i][1], f[i][2] ，那么：

f[i][0] = min{f[i-1][1] + cost[i-1][0], f[i-1][2] + cost[i-1][0]}
f[i][1] = min{f[i-1][0] + cost[i-1][1], f[i-1][2] + cost[i-1][1]}
f[i][2] = min{f[i-1][0] + cost[i-1][2], f[i-1][1] + cost[i-1][2]}

（注意兩個(gè) i-1 的含義是不同的骗污，我們的 i 指的是油漆 i 棟房子崇猫，f(i-1)指的是油漆 i-1 棟房子，而cost[i-1][0]指的是油漆第 i 棟房子為紅色的花費(fèi)需忿，因?yàn)樵跀?shù)組里是從0開始計(jì)數(shù)的诅炉，油漆房子是從1開始計(jì)數(shù)的蜡歹。）

第三步：初始條件和邊界情況

• 初始條件：f[0][0] = f[0][1] = f[0][2] = 0 即不油漆任何房子的花費(fèi)。
• 無邊界情況

第四步：計(jì)算順序

設(shè)油漆前i棟房子并且房子 i 是紅色涕烧、藍(lán)色月而、綠色的最小花費(fèi)分別為f[i][0], f[i][1], f[i][2]
? 初始化f[0][0], f[0][1], f[0][2]
? 計(jì)算f[1][0], f[1][1], f[1][2]
…
? 計(jì)算f[N][0], f[N][1], f[N][2]
? 答案是min{f[N][0], f[N][1], f[N][2]}。時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(N)

代碼如下：

def paint_house(n, costs):
    states = [[0, 0, 0]] + costs  # 在原數(shù)組改動议纯，降低空間復(fù)雜度
    for i in range(1, n+1):
        states[i][0] += min(states[i-1][1], states[i-1][2])
        states[i][1] += min(states[i-1][0], states[i-1][2])
        states[i][2] += min(states[i-1][0], states[i-1][1])
    return min(states[n])

例2. Paint House II

題目描述：
有一排N棟房子父款，每棟房子要漆成 k 種顏色中的一種，任何兩棟相鄰的房子不能漆成同樣的顏色瞻凤。第 i 棟房子染成第 j 種顏色的花費(fèi)是cost[i][j]憨攒。問最少需要花多少錢油漆這些房子？
例子：
輸入： N=3, k=3 ; Cost = [[14,2,11],[11,14,5],[14,3,10]]
輸出：10 （第0棟房子藍(lán)色阀参，第1棟房子綠色肝集，第2棟房子藍(lán)色, 2+5+3=10）

分析：
這題和Paint House非常類似,只是顏色種類變成K種，動態(tài)規(guī)劃思路和Paint House一樣,需要記錄油漆前 i 棟房子并且房子第 i 棟房子是顏色1, 顏色2, ..., 顏色K的最小花費(fèi):f[i][1], f[i][2], ..., f[i][K]蛛壳。設(shè)油漆前i棟房子并且房子 i 是顏色1, 顏色2, ...顏色K的最小花費(fèi)分別為 f[i][1], f[i][2], ..., f[i][K]：
f[i][1] = min{f[i-1][2] + cost[i-1][1], f[i-1][3] + cost[i-1][1], ..., f[i-1][K] + cost[i-1][1]}
f[i][2] = min{f[i-1][1] + cost[i-1][2], f[i-1][3] + cost[i-1][2], ..., f[i-1][K] + cost[i-1][2]}
...
f[i][K] = min{f[i-1][1] + cost[i-1][K], f[i-1][2] + cost[i-1][K], ..., f[i-1][K-1] + cost[i-1][K]}

總之：

但是杏瞻，設(shè)油漆前i棟房子并且房子i-1是顏色1, 顏色2, ...顏色K的最小花費(fèi)分別為f[i][1], f[i][2], ..., f[i][K]
? f[i][j] = min k ≠j {f[i-1][k]} + cost[i-1][j]
? 直接計(jì)算的時(shí)間復(fù)雜度(計(jì)算步數(shù)):
– i從0到N
– j從1到K
– k從1到K
– O(NK 2 )
速度太慢了！

考慮到如果最小值是第 i 個(gè)元素,次小值是第 j 個(gè)元素：

• 只要除掉的元素不是第i個(gè),剩下的最小值就是第 i 個(gè)元素
• 如果除掉的元素是第i個(gè),剩下的最小值就是第 j 個(gè)元素

所以：
? 記錄下f[i-1][1], ..., f[i-1][K]中的最小值和次小值分別是哪個(gè)
? 假如最小值是f[i-1][a], 次小值是f[i-1][b]
? 則對于j=1,2,3,...,a-1, a+1,...,K, f[i][j] = f[i-1][a] + cost[i-1][j]
? f[i][a] = f[i-1][b] + cost[i-1][a]
? 時(shí)間復(fù)雜度降為O(NK)

代碼如下：

def paint_house2(n, k, costs):
    states = [[0]*k] + costs
    for i in range(1, n+1):
        cp = states[i-1].copy()
        cp.sort()
        min_num = cp[0]
        next_num = cp[1]
        idx = states[i-1].index(min_num)
        for j in range(k):
            if j != idx:
                states[i][j] += min_num
            else:
                states[i][j] += next_num
    return min(states[n])

例3. House Robber

題目描述：
有一排N棟房子(0~N-1),房子i里有A[i]個(gè)金幣衙荐。一個(gè)竊賊想選擇一些房子偷金幣捞挥，但是不能偷任何挨著的兩家鄰居,否則會被警察逮住。最多偷多少金幣忧吟？
? 例子:
? 輸入:A={3, 8, 4}
? 輸出:8 (只偷第二家的金幣)

分析：
? 最后一步:竊賊的最優(yōu)策略中,有可能偷或者不偷最后一棟房子N
? 情況1:不偷房子N
– 簡單,最優(yōu)策略就是前N-1棟房子的最優(yōu)策略
? 情況2:偷房子N
– 仍然需要知道在前N-1棟房子中最多能偷多少金幣,但是,需要保證不偷第N-2棟房子

用f[i][0]表示不偷房子 i 的前提下,前 i 棟房子中最多能偷多少金幣砌函；
用f[i][1]表示偷房子 i 的前提下,前 i 棟房子中最多能偷多少金幣。
f[i][0] = max{f[i-1][0], f[i-1][1]}瀑罗，因?yàn)椴煌捣孔觟-1,所以房子i-2可以選擇偷或不偷胸嘴；
f[i][1] = f[i-1][0] + A[i-1]雏掠，偷房子i-1,房子i-2必須不偷斩祭。

在不偷房子i-1的前提下,前i棟房子中最多能偷多少金幣等價(jià)于前i-1棟房子最多能偷多少金幣，所以我們可以簡化前面的表示：
? 設(shè)f[i]為竊賊在前i棟房子最多偷多少金幣
? f[i] = max{f[i-1], f[i-2] + A[i-1]}
? 初始條件:
– f[0] = 0 (沒有房子,偷0枚金幣)
– f[1] = A[0]
– f[2] = max{A[0], A[1]}

時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(1)

代碼如下：

 def rob(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        if n == 1:
            return nums[0]
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = nums[0]
        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return dp[n]
            

例4. House Robber II

題目描述：
有一圈N棟房子,房子i-1里有A[i]個(gè)金幣乡话，一個(gè)竊賊想選擇一些房子偷金幣摧玫，但是不能偷任何挨著的兩家鄰居,否則會被警察逮住。最多偷多少金幣绑青？
? 例子:
? 輸入:A={3, 8, 4}
? 輸出:8 (只偷房子1的金幣)

分析：
這題和House Robber非常類似,只是房子現(xiàn)在排成一個(gè)圈诬像，于是房子0和房子N-1成了鄰居,不能同時(shí)偷盜：要么沒偷房子0，要么沒偷房子N-1闸婴。我們可以枚舉竊賊是沒有偷房子0還是沒有偷房子N-1：
情況1:沒偷房子0坏挠。最優(yōu)策略就是竊賊對于房子1~N-1的最優(yōu)策略->化為House Robber;
情況2:沒偷房子N-1。最優(yōu)策略就是竊賊對于房子0~N-2的最優(yōu)策略->化為House Robber邪乍。

代碼如下：

def houseRobber2(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0], dp[1] = 0, nums[1]
        for i in range(2, n):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        answer = dp[n - 1]
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, n - 1):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return max(dp[n - 2], answer)

例5. Best Time to Buy and Sell Stock

題目描述：
已知后面N天一支股票的每天的價(jià)格P 0 , P 1 , ..., P N-1降狠，可以最多買一股賣一股对竣。求最大利潤。
? 例子:
? 輸入:[3, 2, 3, 1, 2]
? 輸出:1 (2買入,3賣出)

分析：
從0到N-1枚舉j,即第幾天賣榜配，時(shí)刻保存當(dāng)前為止(即0~j-1天)的最低價(jià)格P i否纬，最大的P j - P i 即為答案。（千萬別太僵硬５叭臁）

代碼如下：

def maxProfit(prices: List[int]) -> int:
        if len(prices) < 1:
            return 0
        profit = 0
        low = prices[0]
        for price in prices:
            profit = max(profit, price-low)
            low = min(price, low)
        return profit

例6. Best Time to Buy and Sell Stock II

題目描述：
已知后面N天一支股票的每天的價(jià)格P 0 , P 1 , ..., P N-1临燃，可以買賣一股任意多次,但任意時(shí)刻手中最多持有一股。求最大利潤烙心。
? 例子:
? 輸入:[2, 1, 2, 0, 1]
? 輸出:2 (1買入,2賣出,0買入,1賣出)

分析：
最優(yōu)策略是如果今天的價(jià)格比明天的價(jià)格低,就今天買,明天賣(貪心)膜廊。正確性證明可以從這里下手:
如果最優(yōu)策略第10天買,第15天賣,我們可以把它分解成5天,結(jié)果不會變差。

代碼如下：

def maxProfit2(prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        profit = 0
        for i in range(n-1):
            if prices[i] < prices[i+1]:
                profit += prices[i+1] - prices[i]
        return profit

小結(jié)

• 當(dāng)思考動態(tài)規(guī)劃最后一步時(shí), 這一步的選擇依賴于前一步的某種狀態(tài)淫茵。
• 初始化時(shí),f[0]代表前0個(gè)元素/前0天的情況（與坐標(biāo)型動態(tài)規(guī)劃區(qū)別）
• 計(jì)算時(shí),f[i]代表前i個(gè)元素(即元素0~i-1)的某種性質(zhì)

2.2 最長序列型動態(tài)規(guī)劃

題目給定一個(gè)序列
? 要求找出符合條件的最長子序列
? 方法
– 記錄以每個(gè)元素 i 結(jié)尾的最長子序列的長度
– 計(jì)算時(shí),在 i 之前枚舉子序列上一個(gè)元素是哪個(gè)

例1. Longest Increasing Subsequence

題目描述：
給定a[0], ..., a[n-1]溃论，找到最長的子序列0<=i 1 <i 2 <...<i K <n, 使得a[i 1 ]<a[i 2 ]<...<a[i K ],輸出K
例子:
輸入:[4, 2, 4, 5, 3, 7]
輸出:4 (子序列2, 4, 5, 7)

分析：
最后一步
對于最優(yōu)的策略,一定有最后一個(gè)元素a[j]
? 第一種情況：最優(yōu)策略中最長上升子序列就是{a[j]},答案是1
? 第二種情況：子序列長度大于1,那么最優(yōu)策略中a[j]前一個(gè)元素是a[i], 并且a[i] < a[j]。
因?yàn)槭亲顑?yōu)策略,那么它選中的以a[i]結(jié)尾的上升子序列一定是最長的痘昌。

子問題
因?yàn)椴淮_定最優(yōu)策略中a[j]前一個(gè)元素a[i]是哪個(gè),需要枚舉每個(gè)i钥勋，求以a[i]結(jié)尾的最長上升子序列，本來是求以a[j]結(jié)尾的最長上升子序列辆苔，化為子問題: i < j算灸。

狀態(tài)
設(shè)f[j] =以a[j]結(jié)尾的最長上升子序列的長度。

轉(zhuǎn)移方程
f[j] =以a[j]結(jié)尾的最長上升子序列的長度：
f[j] = max{ 1, f[i] + 1| i < j and a[i] < a[j]}
? 計(jì)算f[0], f[1], f[2], ..., f[n-1]
? 答案是max{f[0], f[1], f[2], ..., f[n-1]}
? 算法時(shí)間復(fù)雜度O(n² ),空間復(fù)雜度O(n)

代碼如下：

def lengthOfLIS(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        dp = [1] * n
        dp[0] = 1
        for i in range(1, n):
            subs = [dp[j] for j in range(i) if nums[j] < nums[i]]
            if subs:
                dp[i] = max(subs) + 1
        return max(dp)

O(NlogN)的解法：

tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Doing so will maintain the tails invariant. The the final answer is just the size.

def lengthOfLIS(self, nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) / 2
            if tails[m] < x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size

例2. Russian Doll Envelopes

題目描述：
給定N個(gè)信封的長度和寬度驻啤，如果一個(gè)信封的長和寬都分別小于另一個(gè)信封的長和寬,則這個(gè)信封可
以放入另一個(gè)信封
? 問最多嵌套多少個(gè)信封
? 例子:
? 輸入:[[5,4],[6,4],[6,7],[2,3]]
? 輸出:3 ([2,3] => [5,4] => [6,7])

分析：
最后一步
對于最優(yōu)的策略,一定有最后一個(gè)元素a[j]
? 第一種情況：最優(yōu)策略中最長上升子序列就是{a[j]},答案是1
? 第二種情況：子序列長度大于1,那么最優(yōu)策略中a[j]前一個(gè)元素是a[i], 并且a[i] < a[j]菲驴。
因?yàn)槭亲顑?yōu)策略,那么它選中的以a[i]結(jié)尾的上升子序列一定是最長的。

子問題
因?yàn)椴淮_定最優(yōu)策略中a[j]前一個(gè)元素a[i]是哪個(gè),需要枚舉每個(gè)i骑冗，求以a[i]結(jié)尾的最長上升子序列赊瞬，本來是求以a[j]結(jié)尾的最長上升子序列，化為子問題: i < j贼涩。

狀態(tài)
設(shè)f[j] =以a[j]結(jié)尾的最長上升子序列的長度巧涧。

轉(zhuǎn)移方程
f[j] =以a[j]結(jié)尾的最長上升子序列的長度：
f[j] = max{ 1, f[i] + 1| i < j and a[i] < a[j]}
? 計(jì)算f[0], f[1], f[2], ..., f[n-1]
? 答案是max{f[0], f[1], f[2], ..., f[n-1]}
? 算法時(shí)間復(fù)雜度O(n² ),空間復(fù)雜度O(n)

代碼如下：

def lengthOfLIS(nums: List[int]) -> int:
        n = len(nums)
        if n < 1:
            return 0
        dp = [1] * n
        dp[0] = 1
        for i in range(1, n):
            subs = [dp[j] for j in range(i) if nums[j] < nums[i]]
            if subs:
                dp[i] = max(subs) + 1
        return max(dp)

三、劃分型動態(tài)規(guī)劃

給定長度為N的序列或字符串,要求劃分成若干段：

• 段數(shù)不限遥倦，或指定K段
• 每一段滿足一定的性質(zhì)

做法類似于序列型動態(tài)規(guī)劃谤绳，但是通常要加上段數(shù)信息。一般用f[i][j]記錄前 i 個(gè)元素(元素0~i-1)分成j段的性質(zhì),如最小代價(jià)袒哥。

例1. Decode Ways

題目描述：
有一段由A-Z組成的字母串信息被加密成數(shù)字串缩筛，加密方式為：A->1, B->2, …, Z->26。給定加密后的數(shù)字串S[0…N-1]堡称，問有多少種方式解密成字母串瞎抛？
例子：
輸入： 12
輸出： 2 (AB 或者 L)

第一步：確定狀態(tài)

解密數(shù)字串即劃分成若干段數(shù)字，每段數(shù)字對應(yīng)一個(gè)字母却紧。

• 最后一步
  最后一步或一段一定對應(yīng)一個(gè)字母 A, B, …, 或Z桐臊，這個(gè)字母加密時(shí)變成1, 2, …, 或26钞艇。

• 子問題
  設(shè)數(shù)字串長度為N，要求數(shù)字串前N個(gè)字符的解密方式數(shù)豪硅，需要知道數(shù)字串前N-1和N-2個(gè)字符的解密方式數(shù)哩照。

• 狀態(tài)：設(shè)數(shù)字串S前 i 個(gè)數(shù)字解密成字母串有 f[i] 種方式。

第二步：轉(zhuǎn)移方程

設(shè)數(shù)字串S前 i 個(gè)數(shù)字解密成字母串有 f[i] 種方式：

f[i] = f[i-1] | S[i-1]對應(yīng)一個(gè)字母 + f[i-2] | S[i-2]S[i-1]對應(yīng)一個(gè)字母懒浮。

第三步：初始條件和邊界情況

• 初始條件：f[0] = 1飘弧，即空串有1種方式解密，解密成空串
• 邊界情況：如果i = 1, 只看最后一個(gè)數(shù)字砚著，f[1] = 1

第四步：計(jì)算順序

依次計(jì)算 f[0], f[1], …, f[N]
? 答案是f[N]
? 時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(N)

代碼如下：

def numDecodings(s: str) -> int:
        if s == "" or s[0] == '0':
            return 0
        s = ' ' + s  # 為了把f(0) = 0 帶入計(jì)算次伶，將 s 延長 1
        dp = [1, 1]  # 初始化 f(0) 和 f(1)
        for i in range(2, len(s)):
            if 10 <= int(s[i-1 : i+1]) <=26 and s[i] != '0':
                dp.append(dp[i-1] + dp[i-2])
            elif s[i-1 : i+1] == '10' or s[i-1 : i+1] == '20':
                dp.append(dp[i-2])
            elif s[i] != '0':  # 零只能用來構(gòu)成 10 或 20，否則無法解碼
                dp.append(dp[i-1])
            else:
                return 0
        return dp[len(s)-1]

例2. Perfect Squares

題目描述：
給定一個(gè)正整數(shù)n稽穆，問最少可以將n分成幾個(gè)完全平方數(shù)(1,4,9,...)之和冠王？
例子：
輸入： n=13
輸出： 2 (13=4+9)

第一步：確定狀態(tài)

• 最后一步
  關(guān)注最優(yōu)策略中最后一個(gè)完全平方數(shù) j²，最優(yōu)策略中n-j² 也一定被分成最少的完全平方數(shù)之和舌镶。
• 子問題
  所以需要知道n-j² 最少被分成幾個(gè)完全平方數(shù)之和柱彻。原來是求 n 最少被分成幾個(gè)完全平方數(shù)之和。
• 狀態(tài)：設(shè) f[i] 表示 i 最少被分成幾個(gè)完全平方數(shù)之和

第二步：轉(zhuǎn)移方程

設(shè)f[i]表示i最少被分成幾個(gè)完全平方數(shù)之和：

第三步：初始條件和邊界情況

初始條件：0被分成0個(gè)完全平方數(shù)之和餐胀，f[0] = 0

第四步：計(jì)算順序

依次計(jì)算 f[0], f[1], …, f[N]
? 答案是f[N]
? 時(shí)間復(fù)雜度O(N^1.5), 空間復(fù)雜度O(N^1.5)

代碼如下：

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

例3. Palindrome Partitioning II

題目描述：
給定一個(gè)字符串S[0..N-1]哟楷，要求將這個(gè)字符串劃分成若干段,每一段都是一個(gè)回文串(正反看起來一樣)。求最少劃分幾次否灾？
例子:
輸入: “aab”
輸出: 1 (劃分1次 “aa”, “b”)

第一步：確定狀態(tài)

• 最后一步
  關(guān)注最優(yōu)策略中最后一段回文串卖擅，設(shè)為S[j..N-1]
• 子問題
  求S前N個(gè)字符S[0..N-1]最少劃分為幾個(gè)回文串，需要知道S前 j 個(gè)字符[0..j-1]最少可以劃分成幾個(gè)回文串墨技，減小問題規(guī)模惩阶。
• 狀態(tài)
  設(shè)S前 i 個(gè)字符S[0..i-1]最少可以劃分成 f[i] 個(gè)回文串。

第二步：轉(zhuǎn)移方程

注意：f[i] 表示前 i 個(gè)字符可以劃分成多少回文字符串扣汪，這里的 i 指字符串長度。f[i-1] 表示前 i-1 個(gè)字符可以分成多少個(gè)脐嫂；而 S[j..i-1] 是下標(biāo)紊遵，比如 j=i-1 時(shí)，f[i-1]如前所述侥蒙，而S[i-1..i-1]指的是最后那個(gè)字符暗膜。

如何判斷回文字符串鞭衩？

可以用兩個(gè)指針從兩頭向中間移動,每一步兩個(gè)指針指向的字符都必須相等娃善。但是每次都判斷S[j..i-1]是不是回文串很慢，可以用 isPalin[i][j] 記錄S[i..j]是否是回文串瑞佩，這樣在主程序內(nèi)直接檢查即可聚磺。轉(zhuǎn)移方程變?yōu)椋?/p>

第三步：初始條件和邊界情況

初始條件：空串被分成0個(gè)回文串炬丸，f[0] = 0

第四步：計(jì)算順序

依次計(jì)算 f[0], f[1], …, f[N]
? 答案是f[N]-1 ，因?yàn)閒[i]是劃分多少回文串稠炬，而問題是劃分多少次。（f[0]除外）
? 時(shí)間復(fù)雜度O(N²), 空間復(fù)雜度O(N²)

代碼如下：

def minCut(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    # 記錄回文字符串
    P = [[False]*n for _ in range(n)]
    for i in reversed(range(n)):
        for j in range(i, n):
            if (s[i] == s[j] and (j - i < 2 or P[i + 1][j - 1])):
                P[i][j] = True
    # 尋找最少劃分
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2, n+1):
        temp = [dp[j]+1 for j in range(i) if P[j][i-1]]
        dp[i] = min(temp)
    return dp[n]-1