0 背景
從（完）零（全）開（忘）始（記）溫（不）習(xí)（會(huì)）動(dòng)（做）態(tài)（題）規(guī)（?。﹦潯?/p>
1 動(dòng)態(tài)規(guī)劃理解
如果一類活動(dòng)過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策(采取措施)，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動(dòng)路線，則稱它為多階段決策問題。
各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.
？？？啥意思？？
下面這一段，我感覺解釋并不是很清楚。。所以暫且劃掉了
舉個(gè)例子，以王者農(nóng)藥來說，
選人的時(shí)候 我們可以選擇‘良好的陣容搭配’或者'想玩什么玩什么'
前期的時(shí)候 我們可以選擇'猥瑣發(fā)育，別浪'或者‘全體進(jìn)攻中路’
中期的時(shí)候 我們可以選擇‘穩(wěn)住我們能贏’、'進(jìn)攻暗影主宰'、'全體進(jìn)攻中路'、'猥瑣發(fā)育，別浪'、'清理兵線'、‘投降’
后期的時(shí)候 。。。
在每一步中我們都可以選擇不同的策略，每一步都策略都基于前一步的選擇，并且也會(huì)影響后面的步驟。
例如
策略：（‘良好的陣容搭配’（決策）+‘猥瑣發(fā)育’（決策）+‘穩(wěn)住我們能贏’（決策））= 白金（效果）
。。。
值得注意的是，我們不是每一步都要選擇最優(yōu)的決策，因?yàn)?，可能?dāng)前決策不是最好的，但是我們最終效果確實(shí)最好的。
例如
'良好的陣容搭配'是選人最好的決策，但是我就只會(huì)玩阿珂，魔都第一阿珂，但是已經(jīng)有刺客了，我還是會(huì)選阿珂（決策），因?yàn)檫x了阿珂就贏了。。（只是舉個(gè)例子），雖然在選人階段我們沒有選擇最優(yōu)的決策，但是我們最后的效果是最好的。
2 思路
基于上面的理解，我們做題該如何去做呢？
1.將大問題拆解為一個(gè)個(gè)的子問題，
2.求解每個(gè)子問題，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)到時(shí)直接存取，不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間
3.自下而上的計(jì)算
3 題目
某廠筆試題目，大概題意，排成一行的正方形，每個(gè)正方形已經(jīng)被染成紅色或者綠色?，F(xiàn)在可以選擇任意一個(gè)正方形然后用這兩種顏色的任意一種進(jìn)行染色，這個(gè)正方形的顏色將會(huì)被覆蓋。目標(biāo)是在完成染色之后，每個(gè)紅色R逗比每個(gè)綠色G距離最左側(cè)近，最少需要染幾個(gè)正方形。
樣例 s=RGRGR
我們涂色之后變成RRRGG滿足要求，涂染的次數(shù)是2，沒有比這個(gè)更好的涂染方案了（這是原題的話，其實(shí)還有別的涂染方案呀，RGGGG也是2次，RRRRR也是2次）
輸入描述：
輸入包括一個(gè)字符串S，字符串s的長度（1<=length<=50）,其中包括'R'或者‘G’，分別表示紅色和綠色
輸出描述
輸出一個(gè)整數(shù)，表示最少需要涂染的正方形數(shù)量
4 題目分析
其實(shí)這道題在字符串很短的時(shí)候，我們用人腦很好思考，
例如
RGGGR 我們只需要把最后一個(gè)R涂成G即滿足要求
RGRRR 我們只需要吧第二個(gè)G涂成R即滿足要求
但是我們怎么將我們腦子里面的計(jì)算方法轉(zhuǎn)換成電腦能識(shí)別的程序語言呢？畢竟當(dāng)字符串的數(shù)量很多的時(shí)候，我們也沒有辦法用我們的大腦很快計(jì)算出結(jié)果。例如
RGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRRRGRGRRRRGGGGGRGRGGRRRR
言歸正傳，用動(dòng)態(tài)規(guī)劃的想法去思考這道題呢？
輸入RGGGR，
我們這道題的子問題是什么呢？就是每一個(gè)方塊該涂什么顏色，自下而上，那我們這里就是自左而右
第一個(gè)R，我們有兩種決策,這個(gè)次數(shù)我們要記下來
1.1.涂成R （0次）
1.2.涂成G（1次）
第二個(gè)G，我們?nèi)杂袃煞N決策，而到這一步的決策我們需要的次數(shù)就要跟上一步有關(guān)了
2.1 涂成R
如果上一次使用1.1的策略我們只需要把第二個(gè)G涂成R即可，也就是1次， 如果上一次使用1.2的策略我們需要把第一個(gè)先涂成R，再把第二個(gè)G涂成R也就是2次，這里我們肯定選擇1.1的策略，因?yàn)檫x擇1.1或者選擇1.2，到了2.1，前兩個(gè)的正方形都是RR所以我們選擇1.2的策略 劃橫線的說法是不對(duì)的，每一小步的決策不能修改上一步的決策，意思是什么呢？如果我們這一步選擇2.1我們就在1.2的基礎(chǔ)上了，因?yàn)镽必須在G的左邊（1次）
2.2 涂成G
如果上一次使用1.1的策略我們本來就是RG所以是0次，如果使用1.2的策略我們是GG所以要把第一個(gè)G涂成R，是1次，所以我們肯定選擇1.1，為什么說肯定呢，到第三個(gè)方塊的時(shí)候，它已經(jīng)不關(guān)心第一個(gè)方塊到到底是R還是G了，因?yàn)榈诙€(gè)方塊是G，它已經(jīng)給第三個(gè)方塊提供了決策的基礎(chǔ)，所以我們只需要在這一步上選擇最優(yōu)的（0次）
第三個(gè)G
3.1涂成R
如果上一次使用2.1的話，我們只需要將第三個(gè)涂成R也就是再增加一次2次，如果上一次使用2.2，我們不能選擇3.1（2次）
3.2涂成G
如果上一次使用2.1的話，我們就在2.1的基礎(chǔ)上+0也就是1次，如果上一次使用2.2的話，我們在2.2的基礎(chǔ)上+0也就是0次，選擇最優(yōu)的（0次）
第四個(gè)G
4.1涂成R
如果上一次使用3.1的話，我們只需要將第三個(gè)涂成R也就是再增加一次3次，如果上一次使用3.2，我們不能選擇4.1（3次）
4.2涂成G
如果上一次使用3.1的話，我們就在3.1的基礎(chǔ)上+0也就是2次，如果上一次使用3.2的話，我們在3.2的基礎(chǔ)上+0也就是0次，選擇最優(yōu)的（0次）
第五個(gè)G
5.1涂成R
如果上一次使用4.1的話，我們只需要將第三個(gè)涂成R也就是再增加0次3次，如果上一次使用4.2，我們不能選擇5.1（3次）
5.2涂成G
如果上一次使用3.1的話，我們就在3.1的基礎(chǔ)上+1也就是4次，如果上一次使用3.2的話，我們在3.2的基礎(chǔ)上+1也就是1次，選擇最優(yōu)的（1次）
如果我們到這里結(jié)束，我們只需要比較5.1和5.2的大小，選擇小的就是5.2
5 代碼
import java.util.Scanner;
public class dpTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
int len = input.length();
int[][] dp = new int[2][len+1];
dp[0][0] = input.charAt(0) == 'R' ? 0 : 1;
dp[1][0] = input.charAt(0) == 'R' ? 0 : 1;
for (int i = 1; i < len; ++i) {
dp[0][i] = dp[0][i - 1] + (input.charAt(i) == 'R' ? 0 : 1);
dp[1][i] = Math.min(dp[1][i - 1], dp[0][i - 1]) + (input.charAt(i) == 'R' ? 1 : 0);
}
//如果你想詳細(xì)看dp的情況可以把下面的注釋去掉
// for (int[] ints : dp) {
// for (int anInt : ints) {
// System.out.print(anInt + "\t");
// }
// System.out.println();
// }
System.out.println(Math.min(dp[0][len - 1], dp[1][len - 1]));
}
}
希望自己能給和自己一樣菜的同學(xué)，一點(diǎn)點(diǎn)生存的空間，歡迎熱烈討論
我是加薪貓
技術(shù)是加薪的前提，生活是加薪的意義
技術(shù)等于生活
