動(dòng)態(tài)規(guī)劃(Dynamic Programming)在上學(xué)的時(shí)候就沒怎么懂，今天又學(xué)習(xí)了一番毅臊，但肯定不可能在一兩個(gè)小時(shí)內(nèi)學(xué)懂理茎、講清楚，所以這篇日報(bào)可能是比較粗淺的理解管嬉，后續(xù)可能會(huì)補(bǔ)充皂林。
動(dòng)態(tài)規(guī)劃把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系蚯撩，逐個(gè)求解础倍。
為了幫助理解，我們可以回憶一下高中時(shí)候?qū)W過的數(shù)學(xué)歸納法胎挎；
最簡單和常見的數(shù)學(xué)歸納法是證明當(dāng)n等于任意一個(gè)自然數(shù)時(shí)某命題成立沟启。證明分下面兩步：
- 證明當(dāng)n= 1時(shí)命題成立忆家。
- 假設(shè)n=m時(shí)命題成立，那么可以推導(dǎo)出在n=m+1時(shí)命題也成立德迹。（m代表任意自然數(shù)）
比如我們證明：
我們會(huì)用一個(gè)遞推得到n=k+1時(shí)成立芽卿，但是必須要用到第二步里的歸納的假設(shè)，不能利用消項(xiàng)把n = k 的這個(gè)假設(shè)給拆掉浦辨。
數(shù)學(xué)歸納法跟動(dòng)態(tài)規(guī)劃有什么聯(lián)系蹬竖？
動(dòng)態(tài)規(guī)劃最重要的一步就是構(gòu)造「狀態(tài)轉(zhuǎn)移方程」（也有人說是怎么拆分問題最重要沼沈，我感覺差不多是一個(gè)意思）流酬。
9 * n
怎么構(gòu)造狀態(tài)轉(zhuǎn)移方程？比如計(jì)算9 * n列另，用dp(n) 表示 9 * n芽腾；
9 * 0 = 0 ;
9 * 1 = 0 + 9;
9 * 2 = 0 + 9 + 9;
用數(shù)學(xué)歸納法可以證明：9 * n=0 + 9 + ... + 9，n個(gè)9页衙；有
dp(0)=9 * 0=0摊滔；
dp(1)=9 * 1=dp(0) + 9；
dp(2)=9 * 2=dp(1) + 9店乐；
那么狀態(tài)轉(zhuǎn)移方程就是：
dp(n) = dp(n-1) + 9
最長遞增子串(Longest Increasing Subsequence)
這是典型的動(dòng)態(tài)規(guī)劃問題艰躺，
求數(shù)列的最長上升（遞增）子數(shù)列（LIS）的長度.
以1 7 2 8 3 4為例，
這個(gè)數(shù)列的最長遞增子數(shù)列是 1 2 3 4眨八，長度為4腺兴；
次長的長度為3， 包括 1 7 8; 1 2 3 等.
我們一眼就能看出答案是1廉侧，2页响，3，4段誊；那我們的腦子是怎么工作的闰蚕？首先我們看到了1，加入隊(duì)列连舍；然后看到7没陡，可以，下面就要找比7大的了索赏，啊盼玄，8可以。這長度只有3参滴，是IS但不是LIS啊强岸。然后我們繼續(xù)從頭開始找，找到了LIS1234砾赔。注意蝌箍，我們找找的了7之后找8青灼，只要找第一個(gè)比7的大的數(shù)字了，不需要管7前面的數(shù)字妓盲。第i個(gè)階段的最優(yōu)解是由前i-1個(gè)階段的最優(yōu)解得到的杂拨，狀態(tài)轉(zhuǎn)移方程是：
LIS(i)=max{LIS(j)+1} ，j<i and a[j] < a[i]
注意后面的條件悯衬，j<i說明j最大可以取到i前面的一個(gè)數(shù)弹沽；a[j]<a[i]說明j后面一定有個(gè)數(shù)字可以增加LIS的大小。
動(dòng)態(tài)規(guī)劃與貪心法的一大區(qū)別是筋粗，動(dòng)態(tài)規(guī)劃有「無后效性」策橘。「無后效性」指狀態(tài)間的轉(zhuǎn)移與如何到達(dá)某狀態(tài)無關(guān)。
每個(gè)階段的最優(yōu)狀態(tài)可以從之前某個(gè)階段的某個(gè)或某些狀態(tài)直接得到而不管之前這個(gè)狀態(tài)是如何得到的->動(dòng)態(tài)規(guī)劃娜亿。
每個(gè)階段的最優(yōu)狀態(tài)都是由上一個(gè)階段的最優(yōu)狀態(tài)得到的->貪心丽已；
另外，動(dòng)態(tài)規(guī)劃除了動(dòng)態(tài)轉(zhuǎn)移方程买决，還有一個(gè)特性沛婴，空間換時(shí)間，你需要記錄之前子過程的最優(yōu)解督赤。比如之前的9 * n嘁灯，如果你知道了9 * (n - 1)，再利用轉(zhuǎn)移方程+9躲舌，瞬間就能得到結(jié)果了丑婿。
LIS的實(shí)現(xiàn)也用到了保存狀態(tài)。而且保存的是每個(gè)位置的LIS孽糖，不能只保存前一個(gè)LIS枯冈，為什么，因?yàn)楦鶕?jù)狀態(tài)轉(zhuǎn)移方程：LIS(i)=max{LIS(j)+1} 办悟，j<i and a[j] < a[i]尘奏；
我們不但需要判斷a[j]<a[i]，還要判斷LIS[j]+1>LIS[i]啊病蛉，注意這個(gè)LIS[j]是從0~j的所有LIS炫加，所以要保存之前每一個(gè)狀態(tài)的LIS。
我就不貼代碼了铺然，看了一個(gè)三哥的視頻俗孝，講得不錯(cuò)，two pointers：
https://www.youtube.com/watch?v=CE2b_-XfVDk&t=311s&index=2&list=PLEd3CfWahaO09NWR8_0VLMqtrLxtm2DpJ
25 July 2017 Review
0/1背包
背包問題是講解貪心和動(dòng)歸的好問題魄健，而且有很多變種赋铝，比如物品可否分割（不能分割的就是0/1背包，要么選要么不選沽瘦；可以分割的就不是0/1背包問題）革骨，同一重量的物品有多件等等农尖。0/1背包指的是物品不能分隔并且同一重量的物品只有一件。
昨天晚上跟著之前講解LIS的那個(gè)三哥的視頻過了一遍0/1 Knapsack Problem良哲，01背包問題盛卡，確實(shí)講得非常清楚，DP就是這樣筑凫，別人跟你講了思路你就覺得清晰明了滑沧，自己想?yún)s很難構(gòu)造最優(yōu)子結(jié)構(gòu)和狀態(tài)轉(zhuǎn)移方程。
三哥先是簡單地提了一下非01背包巍实，也就是物品可以split的情況滓技。這種情況只要拿val/wt用non-increasing的順序pick物品，如有需要蔫浆，把最后一件能裝的物品split一下就行了殖属，這是貪心的思想。01背包就成了一道二維DP的問題瓦盛。
構(gòu)造一個(gè)二維Matrix dp[][]，每一行 i 代表每件物品選或不選外潜，列 j 代表背包的容量從小到大原环。
dp[i][j]表示編號(hào)i以及i之前的物品都可以選擇拿或者不拿，背包容量為j的情況下处窥，最大能裝的val嘱吗。
狀態(tài)轉(zhuǎn)移方程：
dp[i][j] = Max(dp[i-1][j]) , val[i] + dp[i-1][j - wt[i] ])
我有個(gè)疑問是，這個(gè)wt是否要按照greedy的方式來排列滔驾，應(yīng)該是不要的谒麦。
完全背包
同一件物品可以選擇多件。
和01背包問題唯一不同的是j是從1到M哆致。01背包問題是在前一個(gè)子問題（i-1種物品）的基礎(chǔ)上來解決當(dāng)前問題（i種物品）绕德，向i-1種物品時(shí)的背包添加第i種物品；而完全背包問題是在解決當(dāng)前問題（i種物品）摊阀，向i種物品時(shí)的背包添加第i種物品耻蛇。
References:
[1]https://www.zhihu.com/question/23995189
[2]http://www.cnblogs.com/hapjin/p/5597658.html
