474芽唇、一和零
給定一個(gè)包含 L 二進(jìn)制字符串的二維數(shù)組 strs载慈，求零的個(gè)數(shù)不超過 m丛晦，且一的個(gè)數(shù)不超過 n 的最大字符串個(gè)數(shù)谆构。
該問題為零一背包問題谅河，即背包中最多有 m 個(gè) 0 和 n 個(gè) 1老虫。
第一種解法可定義一個(gè)三維數(shù)組 dp[L+1][m+1][n+1]叶骨，dp[i][j][k] 表示前 i 個(gè)字符串中，零的個(gè)數(shù)不超過 j祈匙，且一的個(gè)數(shù)不超過 k 的最大字符串個(gè)數(shù)忽刽。設(shè)第 i 個(gè)字符串的零一個(gè)數(shù)分別為 zero, one，那么：

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one])

其中 max 函數(shù)對(duì)兩種情況取最大值夺欲，前一種是不采用第 i 個(gè)字符串跪帝，后一種是采用第 i 個(gè)字符串。
優(yōu)化解法：code
定義二維數(shù)組 dp[m+1][n+1]些阅，因?yàn)樵诘谝环N解法中伞剑，對(duì)第 i 個(gè)字符串遍歷 k 和 j 求解時(shí)，只會(huì)用到第 i-1 個(gè)求解結(jié)果中 小于等于 k 和 j 位置的值市埋，所以從后向前遍歷 k 和 j黎泣，便可以將三維數(shù)組換位二維數(shù)組。
343缤谎、整數(shù)拆分 code
給定整數(shù)n抒倚，將n拆分為m個(gè)整數(shù)(m>1,且不指定)，求m個(gè)整數(shù)的最大乘積坷澡。
求n的最大乘積與小于n的整數(shù)的最大乘積相關(guān)托呕，因此該問題可通過動(dòng)態(tài)規(guī)劃求解。
定義數(shù)組 dp[n+1]，其中dp[i]表示 i拆分為大于1個(gè)整數(shù)后的最大乘積镣陕。
由于0和1不能拆分谴餐，因此dp[0] = dp[1] = 0.
對(duì)于整數(shù)i，設(shè)其拆出的一個(gè)數(shù)為j呆抑，則剩余的 i-j 可以繼續(xù)拆(i-j繼續(xù)拆的最大乘積前面已求得岂嗓，即dp[i-j])，也可以不拆(即i-j)鹊碍，因此有動(dòng)態(tài)規(guī)劃方程：

dp[i] = max(dp[i], j * (i-j), j * dp[i-j])

其中j需要從0到i-1遍歷厌殉。
121、買賣股票的最佳時(shí)機(jī) code
最多只買一次侈咕，賣一次公罕，求最大收益。
記錄到目前為止的最小價(jià)格耀销。
122、買賣股票的最佳時(shí)機(jī) ii
和上題的不同在于熊尉，可以買賣多次股票，但是上一支股票賣出后才能買下一支股票张吉。
方法一：code1
記錄到目前為止的最小價(jià)格，只要有利潤(rùn)催植，就將股票賣出肮蛹，并將最小價(jià)格記錄為當(dāng)前價(jià)格创南。
方法二：code2
動(dòng)態(tài)規(guī)劃。設(shè)p[i]為第i天(從0開始)的價(jià)格扰藕。
變量dp0記錄當(dāng)天交易完成后不持有股票的最大收益缓苛，dp1記錄當(dāng)天完成交易后持有股票的最大收益。
初始狀態(tài)：
第一天不持有股票的收益為0邓深，持有股票的收益為-p[0]，即

dp0, dp1 = 0, -p[0]

dp0 的狀態(tài)轉(zhuǎn)移方程：
dp0可以從前一天不持有股票(即dp0)轉(zhuǎn)移過來(lái)冬耿，也可以從前一天持有股票(即dp1)并在今天賣掉(利潤(rùn)加上今天的價(jià)格p[i])轉(zhuǎn)移過來(lái)萌壳，即

dp0 = max(dp0, dp1+p[i])

dp1可以從前一天持有股票(即dp1)轉(zhuǎn)移過來(lái)，也可以從前一天不持有股票(即dp0)并在今天買入(利潤(rùn)減去今天的價(jià)格p[i])轉(zhuǎn)移過來(lái)缤骨，即

dp0 = max(dp1, dp0-p[i])

最終的最大利潤(rùn)為 dp0，因?yàn)閺臓顟B(tài)轉(zhuǎn)移方程可以看出 dp0 > dp1精拟。
714虱歪、買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) code
和上題的不同在于，買賣一次股票需要交一定的手續(xù)費(fèi)师枣。
由于手續(xù)費(fèi)的存在萧落，難以采用上題第一種方法，因此采用動(dòng)態(tài)規(guī)劃法拨脉。
198宣增、打家劫舍 code
相鄰的房屋不能一塊搶劫矛缨，否則會(huì)觸發(fā)報(bào)警，求可搶劫的最大收益灵妨。
定義 dp0 表示不搶劫當(dāng)前房屋的最大收益落竹，dp1 代表?yè)尳佼?dāng)前房屋的最大收益。第 i 間房屋的財(cái)產(chǎn)為 nums[i]朱转。
初始狀態(tài)：
不搶劫第0間房屋的收益為0积暖，搶劫第一件房屋的收益為nums[0]，因此：

dp0, dp1 = 0, nums[0]

狀態(tài)轉(zhuǎn)移方程：
截止到第 i 間房屋缅疟，不搶劫該房屋的最大收益可由搶劫第i-1間房屋的最大收益，或者不搶劫第 i-1 間房屋的最大收益轉(zhuǎn)移過來(lái)耘斩；搶劫該房屋的最大收益桅咆，只能由不搶劫第i-1間房屋的最大收益加上當(dāng)前房屋的財(cái)產(chǎn)數(shù)轉(zhuǎn)移過來(lái)轧邪。

dp0, dp1 = max(dp0, dp1), dp[0] + nums[i]

最終的最大收益為 max(dp0, dp1)
213、打家劫舍 ii code
和上題不同之處在于曲管，首尾的房屋是相連的硕糊，也不能一塊搶劫。
由于首位房屋不能一塊搶劫檬某，因此或者不搶劫第一間螟蝙，或者不搶劫最后一間，則轉(zhuǎn)化成了兩種上題的情況场斑，再在這兩種情況間取最大值牵署。
718、最長(zhǎng)重復(fù)子數(shù)組
給定兩個(gè)數(shù)組青责，求最長(zhǎng)的公共子數(shù)組(子數(shù)組是連續(xù)的)的長(zhǎng)度取具。
方法一：code1
在兩個(gè)數(shù)組分別遍歷子數(shù)組的開始位置者填，再求取連續(xù)子數(shù)組長(zhǎng)度。
結(jié)果超時(shí)心墅，時(shí)間復(fù)雜度O(n^3)。
方法二：cod2
動(dòng)態(tài)規(guī)劃瘫筐。dp[i][j]代表以A數(shù)組的第i個(gè)元素結(jié)尾的子數(shù)組铐姚，與以B數(shù)組的第j個(gè)元素結(jié)尾的子數(shù)組的最大公共子數(shù)組的長(zhǎng)度。
狀態(tài)轉(zhuǎn)移方程：
當(dāng)A[i]==B[j]時(shí)之众，dp[i][j]=dp[i-1][j-1]+1依许，否則無(wú)公共子數(shù)組，dp[i][j]=0膘婶。
改進(jìn)：code3
由于dp[i][j]只與dp[i-1][j-1]有關(guān)蛀醉，因此可以定義一維數(shù)組dp拯刁，注意遍歷j時(shí)要從大到小，否則從小到大會(huì)改變j-1的值逸绎。另外注意A[i]!=B[j]時(shí)夭谤，需要將dp[j]賦值為0巫糙。
494、目標(biāo)和
給定一個(gè)由非負(fù)整數(shù)組成的數(shù)組醉锄，每個(gè)元素被賦予正號(hào)或負(fù)號(hào)浙值，求可以實(shí)現(xiàn)和為S的方法數(shù)开呐。
方法一：code1
使用dfs搜索规求。結(jié)果超時(shí)卵惦。時(shí)間復(fù)雜度：O(2^n),空間復(fù)雜度O(n)
方法二：code2
設(shè)數(shù)組大小為N沮尿。由于題目說(shuō)明所有數(shù)組的和不大于1000，因此定義數(shù)組 dp[N][2001]赴邻，dp[i][j]代表前i個(gè)元素可實(shí)現(xiàn)和為j的種類數(shù)啡捶。i從0開始，dp數(shù)組全部初始化為0.
初始化：
由于前0個(gè)元素可實(shí)現(xiàn)和為nums[i]和-nums[i]徒溪，因此

dp[0][nums[i]+1000] += 1
dp[0][-nums[i]+1000] += 1

加1000是因?yàn)閖在數(shù)組中對(duì)應(yīng)下標(biāo)j+1000金顿，例如-1000對(duì)應(yīng)0揍拆。
狀態(tài)轉(zhuǎn)移方程：
前i個(gè)元素和為j可由前i-1個(gè)元素和為j-nums[i]和前i-1個(gè)元素和為j+nums[i]兩種情況轉(zhuǎn)移過來(lái)，
因此：

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

或者前i-1個(gè)元素和為j可轉(zhuǎn)移到前i個(gè)元素和為j-nums[i]和前i個(gè)元素和為j+nums[i]這兩種情況：(在程序中最好加上 if dp[i-1][j+1000] > 0:播揪，因?yàn)閖-nums[i]+1000可能小于0筒狠，而python負(fù)索引時(shí)會(huì)從后往前尋找元素)

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

結(jié)果：dp[-1][S+1000]
時(shí)間復(fù)雜度：O(2001n),空間復(fù)雜度O(2001n)
空間復(fù)雜度優(yōu)化：code3
由于dp[i][j]只與dp[i-1]相關(guān)辩恼，因此可用兩個(gè)數(shù)組代替。注意無(wú)法使用一個(gè)數(shù)組實(shí)現(xiàn)疆前，因?yàn)閐p[i][j]需要訪問dp[i-1]中小于j的元素聘萨，也需要訪問大于j的元素，正序或者倒序訪問數(shù)組都不行。
進(jìn)一步優(yōu)化：code4
使用固定的長(zhǎng)度為2001是數(shù)組不太合理，因?yàn)楹芏鄿y(cè)試實(shí)例的和可能比較小征冷。
因此先求出數(shù)組的和sum检激，然后構(gòu)造大小為2*sum+1的數(shù)組腹侣。
300、最長(zhǎng)遞增子序列 code
設(shè)數(shù)組大小為N饺律，定義數(shù)組dp[N]跺株，dp[i] 代表以nums[i]結(jié)尾的的最長(zhǎng)遞增子序列長(zhǎng)度乒省。
初始化：
dp數(shù)組所有元素賦值為1，因?yàn)槊總€(gè)元素自身為長(zhǎng)為1的序列砸泛。
狀態(tài)轉(zhuǎn)移方程：
對(duì)于dp[i]蛆封，需要遍歷 j < i，如果nums[j] < nums[i]盏筐，則dp[i] = max(dp[i], dp[j]+1)砸讳。
結(jié)果：max(dp)绣夺。
方法二：code2
序列seq初始為[ nums[0] ]欢揖，seq[i]表示長(zhǎng)度為i+1的子序列的末尾元素的最小值她混。遍歷nums中每一個(gè)元素n泊碑，當(dāng)n大于seq[-1]毯欣，將n添加到seq酗钞。否則二分查找seq中第一個(gè)大于等于n的值，替換為n窘奏。最終seq的長(zhǎng)度即最長(zhǎng)遞增子序列的長(zhǎng)度葫录。
參考：1 2
5、最長(zhǎng)回文子串
狀態(tài)轉(zhuǎn)移：若某子串首尾字符不相等骇扇，則肯定不是回文子串面粮；若首尾字符相等但金，則在去掉首位字符的字符為回文子串的情況下，該子串為回文子串钱磅。
定義dp數(shù)組似枕，dp[i][j]代表以i開始以j結(jié)束的子串是否為回文串凿歼。
可以按照字串長(zhǎng)度從小到大計(jì)算：code
或者遍歷開始和結(jié)束下標(biāo)，由于dp[i][j]依賴于dp[i+1][j-1]味赃，因此起始下標(biāo)需要從大到小虐拓。code2
279、完全平方數(shù)
方法一：code1
動(dòng)態(tài)規(guī)劃城榛。定義數(shù)組dp狠持，dp[i]表示數(shù)字i最少由dp[i]個(gè)完全平方數(shù)組成。dp[0]=0.
狀態(tài)轉(zhuǎn)移方程：
dp[i] = min(dp[i], dp[i-squre]+1)甜刻，即設(shè)i的某個(gè)完全平方數(shù)為squre王污，則其余i-squre已求得最少由dp[i-squre]個(gè)完全平方數(shù)組成昭齐，+1即再加上squre。其中squre需要遍歷小于i的所有平方數(shù)就谜。
注意：
在遍歷小于i的所有平方數(shù)時(shí)里覆，若j從1開始逐漸增加，并將j的平方與i相比虹统，會(huì)超時(shí)（可能因?yàn)槠椒竭\(yùn)算較耗時(shí)）车荔。因此首先在squres數(shù)組中預(yù)先保存所有小于n的平方數(shù)戚扳。
方法二：code2
廣度優(yōu)先搜索帽借。第0層為節(jié)點(diǎn)(n,0)，元組第一個(gè)元素為節(jié)點(diǎn)的值蒂教，第二個(gè)元素為深度脆荷。
第1層考慮所有小于n的平方數(shù)，由此可以將深度增加1苔严。逐層增加深度届氢，當(dāng)某層元素為0時(shí)覆旭，則當(dāng)前層深度為最少平方數(shù)個(gè)數(shù)。
注意：需要一個(gè)set記錄遍歷過的值寂祥，因?yàn)橹氨闅v過的值的深度小于等于當(dāng)前層丸凭，所以在當(dāng)前層分解該值的深度肯定大于等于該值在更淺層分解的深度腕铸。
此外，注意用que=deque((n,0))會(huì)將隊(duì)列初始化為兩個(gè)元素虽界。應(yīng)該先que=deque()莉御，然后que.append((n,0))俗冻，則que由元組構(gòu)成。
120晴圾、三角形最小路徑和
方法一：dfs
超時(shí)死姚，存在重復(fù)計(jì)算勤篮。
方法二：dfs+dp
記錄已經(jīng)求得的結(jié)果碰缔，已求得時(shí)，直接返回瀑焦。
方法三：dp
從下往上求，dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]铺董。
每求完一行禀晓，pop掉最后一個(gè)元素粹懒。
1262、可被三整除的最大和 code 參考
定義大小為3的dp數(shù)組确垫，dp[i]表示余數(shù)為i的最大和拣凹，dp初始各元素初始化為0嚣镜。
遍歷每一個(gè)元素n，對(duì)與dp[i]來(lái)說(shuō)付呕，dp[i]+n的余數(shù)會(huì)變成：new_mode=(dp[i]+n)%3徽职，為求最大和佩厚，使dp[new_mode] = max(dp[new_mode], dp[i]+n)。
注意每次遍歷一個(gè)元素n潮瓶，計(jì)算新的dp數(shù)組時(shí)毯辅，需要用上一個(gè)dp數(shù)組的元素計(jì)算煞额，因此代碼中for m in dp[:]產(chǎn)生了舊dp數(shù)組的一個(gè)copy。
注意不要使new_mode=(i+n)%3基跑，因?yàn)閐p[i]的余數(shù)不一定是i（初始化為0）嗜逻，new_mode=(dp[i]+n)%3則不會(huì)有問題栈顷。
1035嵌巷、不相交的線 code
題目要求連線的數(shù)字相等搪哪，各線段不相交，即各線段的兩端點(diǎn)的下標(biāo)在各自數(shù)組都是遞增的惑朦，因此是最長(zhǎng)公共子序列問題漓概。
486胃珍、 預(yù)測(cè)贏家
方法一：遞歸 code1
當(dāng)前的先手有兩種選擇觅彰，應(yīng)該選擇遞歸返回的結(jié)果加上選擇的結(jié)果更大的那個(gè)。
方法二：動(dòng)態(tài)規(guī)劃
在遞歸時(shí)烛芬，先手或后手存在重復(fù)計(jì)算赘娄。因此用dp數(shù)組記錄读拆，dp[i][j][0]、dp[i][j][1]表示第i個(gè)到第j個(gè)元素暑诸，先手个榕、后手分別獲得的最大分?jǐn)?shù)。則先手會(huì)選擇dp[i][j-1][1]+nums[j]和dp[i+1][j][1]+nums[i]中較大的一種凰萨。