動態規劃
暴力遞回之所以暴力是因為存在大量的重復計算，比如一個很經典的問題——斐波那契數列，
public static int fibonacci(int n) {
if(n==1) {
return 1;
}
if(n==2) {
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}
上面的試法，存在大量的重復計算，浪費時間，
由此引出我們的動態規劃，之前寫了8篇暴力遞回的文章，就是為了這個目的，
因為動態規劃就是某一類嘗試行為的進一步優化，任何一個動態規劃的問題都是以某一個暴力嘗試程序中優化后的樣子，
題目
假設有排成一行的N個位置，記為1~N, N一定大于或等于2
開始時機器人在其中的M位置上(M一定是1~N中的一個)
如果機器人來到1位置，那么下一步只能往右來到2位置；
如果機器人來到N位置，那么下一步只能往左來到N-1位置；
如果機器人來到中間位置，那么下一步可以往左走或者往右走；
規定機器人必須走K步，最終能來到P位置(P也是1~N中的一個)的方法有多少種
給定四個引數N、M、K、P，回傳方法數，
題目什么意思呢，我們先自己帶入小的樣本量，方便我們弄懂題意：
假設總共有7個數，一開始，機器人在數字3上面，要求必須走滿3步，最終能來到數字2上面，方法總共有3種，下圖分別列出來：
package com.harrison.class13;
public class Code02_RobotWalk {
// N 只能在1~N范圍上移動 固定引數
// cur 當前來到的位置 可變引數
// rest 還剩多少步要走 可變引數
// P 最終要到的位置 固定引數
// 函式含義：
// 只能在1~N位置上移動，當前在cur位置上，走完rest步后，停在P位置上的方法有多少種
public static int process1(int N,int cur,int rest,int P) {
// 如果沒有剩余步數了，并且來到了目的位置，說明之前的移動方式有效
// 如果沒有剩余步數了，并且沒有來到目的位置，說明之前的移動方式無效
if(rest==0) {
return cur==P?1:0;
}
// if沒中，還剩rest步要走
// 如果來到了1位置，沒得選，只能往右去2位置
// 后續的程序就是來到2位置，還剩rest-1步
if(cur==1) {
return process1(N, 2, rest-1, P);
}
// 如果來到了N位置，沒得選，只能往左去N-1位置
// 后續的程序就是來到N-1位置，還剩rest-1步
if(cur==N) {
return process1(N, N-1, rest-1, P);
}
// 如果還有rest步要走，而當前的cur位置在中間，那么當前這步可以走向左，也可以走向右
// 走向左之后，后續的程序就是，來到cur-1位置上，還剩rest-1步要走
// 走向右之后，后續的程序就是，來到cur+1位置上，還剩rest-1步要走
// 走向左、走向右是截然不同的方法，所以總方法數都要算上
return process1(N, cur-1, rest-1, P)+process1(N, cur+1, rest-1, P);
}
public static int ways1(int N,int M,int K,int P) {
// 引數無效直接回傳0
if(M<1 || M>N || P<1 || P>N || K<1 || N<2) {
return 0;
}
// 總共N個位置，從M點出發，還剩K步，回傳最終能到達P的方法數
return process1(N, M, K, P);
}
public static void main(String[] args) {
System.out.println(ways1(7, 3, 3, 2));
}
}
上述暴力遞回肯定也存在大量的重復計算，
如果我們可以做出一個快取的話，那就不用遞回，可以直接從快取中拿資料來用！
所以，接下來進行優化：
// 把cur和rest的組合，回傳的結果，加入到快取中
public static int process2(int N,int cur,int rest,int P,int[][] dp) {
if(dp[cur][rest]!=-1) {// 不等于-1，表示已經算過，直接從快取中拿值
return dp[cur][rest];
}
if(rest==0) {
// 回傳之前先加快取，底下都這么干
dp[cur][rest]=cur==P?1:0;
return dp[cur][rest];
}
if(cur==1) {
dp[cur][rest]=process2(N, 2, rest-1, P,dp);
return dp[cur][rest];
}
if(cur==N) {
dp[cur][rest]=process2(N, N-1, rest-1, P,dp);
return dp[cur][rest];
}
dp[cur][rest]=process2(N, cur-1, rest-1, P,dp)+process2(N, cur+1, rest-1, P,dp);
return dp[cur][rest];
}
public static int ways2(int N,int M,int K,int P) {
if(M<1 || M>N || P<1 || P>N || K<1 || N<2) {
return 0;
}
// 這張二維表可以把遞回所有的回傳值裝下
int[][] dp=new int[N+1][K+1];
for(int row=0; row<=N; row++) {
for(int col=0; col<=K; col++) {
dp[row][col]=-1;// 表示所有的引陣列合都沒有算過
// 因為如果算過的話，方法數不可能小于0
}
}
return process2(N, M, K, P,dp);
}
在每次暴力遞回之前先在快取中查看是否已經算過，如果已經算過，就直接從快取中拿值，可以省去很多重復計算的程序，這就是動態規劃，它的另一個名字叫做記憶化搜索，是動態規劃中最糙的一種，它不關心狀態的依賴，就是一個很傻的快取，遇到了重復的程序就從快取中拿結果，如果碰到沒算過的程序才去算，
那么經典的動態規劃是怎樣的呢？
經典的動態規劃需要對表進行精細化分析，很明顯上述遞回程序只有兩個可變引數，所以可以看成一個二維表：（在1~7位置上，從2出發，還剩下5步，最終要走到3位置上）
接下來就按我們一開始暴力遞回的思路去填這張表：
1）cur是在1~7上，不存在0，所以第0行全畫叉；
// 如果沒有剩余步數了，并且來到了目的位置，說明之前的移動方式有效
// 如果沒有剩余步數了，并且沒有來到目的位置，說明之前的移動方式無效
if(rest==0) {
return cur==P?1:0;
}
2）cur==1的時候，依賴左下角的位置；
// 如果來到了1位置，沒得選，只能往右去2位置
// 后續的程序就是來到2位置，還剩rest-1步
if(cur==1) {
return process1(N, 2, rest-1, P);
}
3）cur==N的時候，依賴左上角的位置；
// 如果來到了N位置，沒得選，只能往左去N-1位置
// 后續的程序就是來到N-1位置，還剩rest-1步
if(cur==N) {
return process1(N, N-1, rest-1, P);
}
4）除此以外，任何一個普遍位置都依賴左上角和左下角的值，
// 如果還有rest步要走，而當前的cur位置在中間，那么當前這步可以走向左，也可以走向右
// 走向左之后，后續的程序就是，來到cur-1位置上，還剩rest-1步要走
// 走向右之后，后續的程序就是，來到cur+1位置上，還剩rest-1步要走
// 走向左、走向右是截然不同的方法，所以總方法數都要算上
return process1(N, cur-1, rest-1, P)+process1(N, cur+1, rest-1, P);
這么看來，改動態規劃根本不需要知道原來題意是什么，完全根據暴力遞回的思路來改就可以了，也就是說，如果某個人寫了一個二維可變引數的遞回，那么你就可以只根據他的遞回怎么寫就可以改出動態規劃，都不用關心原題意是什么！
接下來根據上述原則把這個二維表格填好，然后根據主函式的呼叫方式回傳（從2出發，還剩下5步）：
附上這道題目兩種方法的完整代碼：
package com.harrison.class13;
public class Code02_RobotWalk {
// N 只能在1~N范圍上移動 固定引數
// cur 當前來到的位置 可變引數
// rest 還剩多少步要走 可變引數
// P 最終要到的位置 固定引數
// 函式含義：
// 只能在1~N位置上移動，當前在cur位置上，走完rest步后，停在P位置上的方法有多少種
public static int process1(int N,int cur,int rest,int P) {
// 如果沒有剩余步數了，并且來到了目的位置，說明之前的移動方式有效
// 如果沒有剩余步數了，并且沒有來到目的位置，說明之前的移動方式無效
if(rest==0) {
return cur==P?1:0;
}
// if沒中，還剩rest步要走
// 如果來到了1位置，沒得選，只能往右去2位置
// 后續的程序就是來到2位置，還剩rest-1步
if(cur==1) {
return process1(N, 2, rest-1, P);
}
// 如果來到了N位置，沒得選，只能往左去N-1位置
// 后續的程序就是來到N-1位置，還剩rest-1步
if(cur==N) {
return process1(N, N-1, rest-1, P);
}
// 如果還有rest步要走，而當前的cur位置在中間，那么當前這步可以走向左，也可以走向右
// 走向左之后，后續的程序就是，來到cur-1位置上，還剩rest-1步要走
// 走向右之后，后續的程序就是，來到cur+1位置上，還剩rest-1步要走
// 走向左、走向右是截然不同的方法，所以總方法數都要算上
return process1(N, cur-1, rest-1, P)+process1(N, cur+1, rest-1, P);
}
public static int ways1(int N,int M,int K,int P) {
// 引數無效直接回傳0
if(M<1 || M>N || P<1 || P>N || K<1 || N<2) {
return 0;
}
// 總共N個位置，從M點出發，還剩K步，回傳最終能到達P的方法數
return process1(N, M, K, P);
}
// 把cur和rest的組合，回傳的結果，加入到快取中
public static int process2(int N,int cur,int rest,int P,int[][] dp) {
if(dp[cur][rest]!=-1) {// 不等于-1，表示已經算過，直接從快取中拿值
return dp[cur][rest];
}
if(rest==0) {
// 回傳之前先加快取，底下都這么干
dp[cur][rest]=cur==P?1:0;
return dp[cur][rest];
}
if(cur==1) {
dp[cur][rest]=process2(N, 2, rest-1, P,dp);
return dp[cur][rest];
}
if(cur==N) {
dp[cur][rest]=process2(N, N-1, rest-1, P,dp);
return dp[cur][rest];
}
dp[cur][rest]=process2(N, cur-1, rest-1, P,dp)+process2(N, cur+1, rest-1, P,dp);
return dp[cur][rest];
}
public static int ways2(int N,int M,int K,int P) {
if(M<1 || M>N || P<1 || P>N || K<1 || N<2) {
return 0;
}
// 這張二維表可以把遞回所有的回傳值裝下
int[][] dp=new int[N+1][K+1];
for(int row=0; row<=N; row++) {
for(int col=0; col<=K; col++) {
dp[row][col]=-1;// 表示所有的引陣列合都沒有算過
// 因為如果算過的話，方法數不可能小于0
}
}
return process2(N, M, K, P,dp);
}
public static void main(String[] args) {
System.out.println(ways1(7, 2, 5, 3));
System.out.println(ways2(7, 2, 5, 3));
}
}
最后來點方法論的總結：
暴力遞回的分析程序抽象出來就是動態規劃的轉義方程，任何一個動態規劃都是由暴力嘗試的嘗試的那個種子改過來的，只要可變引數是有限幾個，三個可變引數就是一張三維表，兩個可變引數就是一張二維表，一個可變引數就是一張一維表，只要能試出由可變引數代表的一個暴力遞回，就可以改成動態規劃，注意：不是所有暴力遞回都能改成動態規劃，但是動態規劃一定來自一個暴力遞回，而暴力遞回是跟自然智慧最貼合的，知道怎么拆，所以比編動態轉義方程容易，
有些暴力遞回改不成動態規劃的原因是它沒有足夠多的重復程序，當然改還是可以改，但是沒有必要，
題 -> 找到暴力遞回的寫法（嘗試）-> 分析暴力遞回程序中是有重復解的（可變引數不講究組織就是記憶化搜索，記憶化搜索進行精細化組織就是經典的動態規劃）
不是所有暴力遞回都能改成動態規劃，但是動態規劃一定來自一個暴力遞回！
不是所有暴力遞回都能改成動態規劃，但是動態規劃一定來自一個暴力遞回！
不是所有暴力遞回都能改成動態規劃，但是動態規劃一定來自一個暴力遞回！
重要的事情說三遍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/397415.html
標籤：其他
上一篇：動態規劃——背包問題