貪心與動态規劃
貪心
貪心政策可以通過樣例去嘗試，寫完以後寫個暴力打表比對，比對成功就可以交了，不要花功夫去證明沒時間。
數論也可以貪心，有時候取一些特殊結論就可以。
藍橋杯 最大最小公倍數
要求xyz/gcd（x,y,z）最小
如果n是奇數，最大三個數n，n-1，n-2是奇偶奇，他們一定互質。最小公倍數就是n(n-1)(n-2)
如果n是偶數，最大三個數n,n-1,n-2是偶奇偶，他們有公因數2.次大三個數是n-1,n-2,n-3是奇偶奇，他們一定互質。是以隻要比較n(n-1)(n-2)/2和(n-1)(n-2)(n-3)大小即可。實際上隻要n>3都是選後者比較好。
有些題目可以用Dp做，如果挖掘到更深刻的性質就是一個貪心問題。
leetcode44 通配符比對
dp做法：
解釋一下第三個式子，當p[j]==’*'我們可以用這個*比對也可以不用這個*（因為他可以代替空字元），兩種隻要一種可以比對成功就比對成功了。
邊界條件：(看做幾種特殊的字元串比對)
dp[0][0]=1 s空p空比對成功
dp[i][0]=0 s非空p空一定無法比對
dp[0][j]=如果s空而p的前j個字元都是*，就比對成功
貪心做法：
觀察模式串:abcd*e?fg*hij
隻要暴力的先找出abcd，從下一個位置再找出e?fg，從下一個位置再找出hij就比對成功了，否則不成功。
貪心關鍵是觀察出一種關鍵的性質，去嘗試用這個性質暴力解題。
相似題目：leetcode 10正規表達式比對。
常見貪心政策
leetcode 376 擺動序列
對一個序列的單調性要敏感，像這種在序列的峰值或者谷值貪心的題目很多。
區間貪心
按頭按尾從左到右從右到左排序。
或者依次序遞推及時判斷。
leetcode 435 無重疊區間
按右邊界排序，選擇最早結束的再安排下一個區間。
leetcode 452 用最少數量的箭引爆氣球
也是按右邊界排序，選擇最早結束的，看他的右邊界與幾個區間有交集，就能穿破幾個氣球。把穿破了的區間跳過，繼續尋找最早結束的，以此類推。
複雜的貪心題目通常會推出一個公式，對這個公式的計算結果排序進行貪心
Acwing125 耍雜技的牛
貪心例題
leetcode 45 跳躍遊戲2
貪心政策：找到每步能跳到的最遠的地方（對現在每個能跳到的地方進行擴充），直到擴充到終點。
leetcode 122 股票買賣的最佳時機
dp做法：
一個狀态機DP。dp[i][0]表示當天手上沒有股票，dp[i][1]表示當天手上有股票。
貪心做法：
因為不限制買賣的次數，隻要a[i]>a[i-1]就在i-1買入，i抛售即可。
類似題目 leetcode188 股票買賣的最佳時機4
這道題有限制隻能買賣k次，是以隻能加入一維k進行dp
leetcode 134 加油站
貪心政策：要想汽車一直跑下去，則需要：
看起來每個位置都可以開始，實際上在斷油處開始才是一種新方案。因為在斷油處前，都滿足gas>cost，直到斷油處都會斷油，證明如下：
是以要多運用數學推算貪心的性質哦。
leetcode 135 分發糖果
貪心政策：分發糖果時，先設給第一個小朋友一顆糖果。之後每個小朋友如果比前一個表現好，糖果數就等于前一個的糖果數加一。
如果沒有前一個小朋友表現好，則在他之前的小朋友糖果數都加一。
leetcode 402移掉k位數字
都是去掉一些使得越小的在前面越好。
leetcode 321 拼接最大數
兩個數組取出的數的長度x，y應當滿足x+y=k
枚舉每個x和y：
1.利用單調棧，可以找到從左/右周遊第一個比它小/大的元素的位置。這裡我們找一個單調遞減的x個的序列湊成第一個數組的取出的數，找一個單調遞減的y個的序列湊成第二個數組取出的數。
2.将兩個合并成最大的序列（有點像歸并排序的操作方式）
3.比較每一組xy看哪個組成的數最大。
leetcode 1081 不同字元的最小子序列
隻要是還有>1個某字母，某字母就可以被丢棄。
那麼丢棄哪些字母呢？實際上也可以做一個類似單調棧的操作，把不單調且還有>1個字母的丢棄。
leetcode 502 IPO
每次選擇最賺錢的項目，然後考慮可達項目即可。
動态規劃基本分類
線性DP
線性Dp經典的就是數組上的dp和字元串dp。
leetcode 53 最大子序和
我們常常把關于某個位置的結論存儲在dp[i]中，最後再取最佳的一個。
比如這道題，某個位置結尾的最大子序和就是
max{前一段最大子序和加上這個數作為一個子序列，自己本身作為一個子序列}
leetcode62 最小編輯距離
兩個字元串對比也經常用DP解決，最小編輯距離應該是兩個字元串對比最經典的題目了。（這其實算一個區間dp）
值得關注的是邊界條件：
dp[i][0]=i 表示進行i次删除操作距離為i
dp[0][j]=j 表示進行j次插入操作距離為j
線性dp常見的還有最長上升子序列的各種變體，通常我們設定一個位置i，f[i]表示i位置最怎樣怎樣的一個屬性，或者是串中以i開頭（結尾）（開頭常常是逆推，結尾是正推，是以常用的是結尾）的最怎樣怎樣的一個屬性。
leetcode 32 最長有效括号
也是個關于串的問題，要落實到串的性質本身。
用f[i]表示第i個位置之前的合法括号長度。
答案就是dp數組的最大值。
leetcode 91 解碼方法
假設一個串s[1…i]需要解碼，那麼如果他最後一位用A~I解碼，s[1…i]解碼的方案數就是s[1…i-1]解碼的方案數。
如果最後兩位用J~Z解碼，s[1…i]解碼的方案數就是s[1…i-2]解碼的方案數。
背包Dp
背包DP是背闆然後稍微根據題意改動即可。這裡參考Acwing的提高課程講的非常全面。
我的總結
狀态機Dp
大多數以時序作為狀态劃分的依據。
舉個例子，沒有上司的舞會，這是個經典的樹形DP，傳遞的時候有狀态0：上一層沒有參加舞會的人
和狀态1：上一層有參加舞會的人
得到這一層的狀态0和狀态1，這就是一個簡單的狀态機模型。
上面提到的買股票的問題：狀态1是在這個時刻買了股票，狀态0是在這個時刻沒有買股票。
藍橋杯 砸手機
由于這個手機有三次砸的機會，就分為三種狀态.0表示沒砸過，1表示砸過一次，2表示砸過兩次。
區間Dp
有點像線段樹的處理方法，考慮兩個區間如何疊加，以及疊加的新耗費。
leetcode 5 最長回文子串
如果一個串p(i,j)是回文的，并且a[i-1]==a[j+1],那麼p(i-1,j+1)就是回文的。
初始條件：1.某個字母肯定是回文的，即p(i,i)=1
2.某兩個連在一起的字母，若是一樣的就是回文的
p(i,i+1)=(a[i]==a[i+1])
對于一個串的問題，可以用i，j組成二維dp，也可以用i，len組成二維dp，看哪個友善用哪個。
leetcode516 最長回文子序列
用f[i][j]表示第i個字元到第j個字元的子串中，最長回文序列的長度。
這道題由f[i+!][j]推得f[i][j]，是以i應當從後往前周遊，而j一定在i+1之後，于是j從i+1開始周遊。
邊界條件f[i][i]=1
leetcode 312 戳氣球
在戳破氣球的過程中，兩邊氣球的左右nums會發生改變。
模拟一下我們在一個區間(i,j)最後步驟需要進行的操作：戳爆一個氣球k，獲得nums[i]*nums[k]*nums[j]個積分。
這樣就可以把區間一分為二(i,k)和(k,j)再繼續進行dp。
邊界情況：f[i][i]=nums[i-1]*nums[i]*nums[i+1]
leetcode 87 擾亂字元串
這題還是挺難的。
對于給出的兩個串S和T，S拆分為子串S1和S2，T拆分為子串T1和T2，有兩種情況：
- 交換：S1能由T2變換得到，S2能由T1變換得到。
- 不交換：S1能由T1變換得到，S2能由T2變換得到。
dp[i][j][k][h]表示s[i…j]能由t[k…h]變換得到。由于有j-i==h-k，是以用len表示長度，就可以把dp數組優化到3維
dp[i][k][len]
x是介于1到len-1的數隻要有一個成功了就行。
dp[i][k][len]=dp[i][k][x]&&dp[i+x][k+x][len-x]
(對應不交換的情況)
or
dp[i][k+len-x][x]&&dp[i+x][k][len-x]
(對應交換的情況，有點繞，要好好了解，區間dp最難的是用有限的變量來表示你想得到的區間)
樹形DP
考慮左右子樹怎麼歸結到根節點即可。
狀壓DP
一般以二進制狀态作為狀态劃分的依據
用位運算表示狀态，一個狀态到另一個狀态的表達式。
狀壓dp常見狀态轉移方程：
假設現在的狀态是state，所在位置v，要去u
枚舉state的子集：
其實就是lowbit操作，找到子集中最後一個1.
把它減去再繼續找，直到減沒了為止。
有兩種狀态壓縮dp的方式：
第一種是棋盤式的狀态壓縮dp，在棋盤裡統計一些值，可能是方案數，可能是最大的數量等等。
（這種狀壓dp會有各種形狀的聯通性）
另一種是集合式的狀态壓縮dp問題，比如哪些點走過設定為1，沒有走過設定為0。
Acwing 1064 小國王
每一行隻和上一行的擺法有關系，和上上行的擺放方式無關。
f[i][k][state]==達到這個狀态的方案數
i:擺放到第i行
k：擺放了k個棋子
state：第i行擺放方式 n位二進制數
什麼樣的狀态能轉移到f[i][k][state]?
1、要上一行合法，不能有兩個相鄰的國王。
2、要上一行和第i行不沖突
3、棋子的數量滿足要求
a&b==0
a|b不能有兩個相鄰的1
f[i][k+cnt(a)][a]+=f[i-1][k][b]
這道題需要預處理狀态a對應的所有狀态b
然後在dp的時候從狀态a對應的狀态b中一個個枚舉狀态b
數位DP
計數DP
其實就是在數組裡面存方案數。
leetcode 63 不同路徑2
f[i][j]=f[i-1][j]+f[i][j-1]
初始條件f[0][0]=1代表能走到0，0就是一種方案。
ACwing 11 背包問題求方案數
#include<iostream>
using namespace std;
const int N=10010;
int cnt[N];
int f[N];
int mod=1000000007;
int main()
{
int n,V;
cin>>n>>V;
for(int i=0;i<V;i++)
{
cnt[i]=1;
}
for(int i=0;i<n;i++)
{
int v,w;
cin>>v>>w;
for(int j=V;j>=v;j--)
{
int value=f[j-v]+w;
if(value>f[j])
{
f[j]=value;
cnt[j]=cnt[j-v];
}
else if(value==f[j])
{
cnt[j]=(cnt[j]+cnt[j-v])%mod;
}
}
}
cout<<cnt[V];
return 0;
}
動态規劃優化
DP與其他資料結構、技巧結合
矩陣遞推（矩陣快速幂）
線段樹+DP
用動态規劃做預處理
**leetcode392 **
leetcode 42 接雨水
這道題要求預處理一個數左邊和右邊比他大的最大的數。