前引：繼上篇我們講到暴力遞歸的過程，這一篇blog我們將繼續(xù)對從暴力遞歸到動態(tài)規(guī)劃的實現(xiàn)過程，與上篇類似，我們依然采用題目的方式對其轉(zhuǎn)化過程進行論述。

上篇博客：https://blog.csdn.net/m0_65431718/article/details/129604874?spm=1001.2014.3001.5502

一.n皇后問題

八皇后問題是十九世紀著名的數(shù)學家高斯于1850年提出的。問題是:在n×n的棋盤上擺放n個皇后，使任意兩個皇后都不能處于同一行、同一列或同一斜線上。

我們的解題思路如下：采用暴力遞歸，既然要求任意兩個皇后不能在同一行和同一列和同一斜線，我們依次對這三者進行討論：①同一行：每一層遞歸代表一行，我們只要保證在每一層遞歸中只放置一個皇后即可②同一列：按照題目的要求，我們在訪擺放第n層的皇后時，要保證它和前面n-1等皇后都不沖突，這就意味著我們在進行下一層遞歸的時候仍能有方法訪問前面皇后擺放的位置：我們的第一考慮對象當然是數(shù)組，但是比較巧妙的是它是一個n*n的棋盤，第一個n代表行，第二個n代表列，我們只需要建立一個長度為n的一維數(shù)組，下標代表第幾行，下標對應(yīng)的數(shù)組元素代表列，作為參數(shù)帶入到下一層遞歸中，斜線也是如此，我們詳細展開說說列和斜線的要求：對于列來說，我們要遍歷緩存，使前面的緩存和當前列不相等即為不沖突，對于斜線的要求來說，對于一個正方形棋盤，我們其實很容易想到的是直線的斜率為1，也就是說兩個元素行的變化如果等于列的變化，我們可以說在同一條斜線上。我們根據(jù)思路給出code：

public class NEmpress {public static void main(String[] args) {//創(chuàng)建dateint n=4;int[]data=new int[n];System.out.println(process(data, 0, n));}//創(chuàng)建遞歸過程public static int process(int[]data,int i,int n){//判斷出口條件:共有n個元素，一旦當前行越過了n-1，則說明成功if(i==n){return 1;}//循環(huán)處理每一列//如果沒結(jié)束int res=0;for(int j=0;j<n;++j){//判斷當前元素是否有效if(isValid(data,i,j)){data[i]=j;//進入下一層遞歸res+= process( data, i+1, n);}}return res;}private static boolean isValid(int[] data, int i, int j) {//在data中檢驗是否存在for(int k=0;k<i;++k){//第一個是判斷從0到i-1行中列的元素是否相等，第二個是判斷是否在同一斜線if(data[k]==j||(Math.abs(i-k)==Math.abs(j-data[k]))){return false;}}return true;}
}

如果不改變問題的實現(xiàn)思路，很難去實現(xiàn)大的效率提升，但是考慮不同的方法仍能在一定程度上提升效率（常數(shù)級提升）：采用位運算，總體的實現(xiàn)邏輯和之前的暴力遞歸完全相同，但是就具體細節(jié)做出了一定的改動，我們給出遞歸的核心代碼，并改動進行解釋說明:

limit:是位數(shù)限制,對于行列數(shù)為N的棋盤，limit的限制是：對于前N個二進制位數(shù)均為1，對于N行列的棋盤而言，前N個二進制位代表棋盤的每一行（第一個二進制位代表第一行，第二個代表第二行........）

①col:對于每次擺放個皇后，就將這個二進制位置變?yōu)?，表示這個二進制位不能擺放皇后了

②leftLim:左斜線限制，如果leftLim為1，代表對于當前行來說，這個位置不能擺放皇后了。

③RightLim:右斜線限制，如果RightLim為1，同樣對于當前行來說，這個位置不能擺放皇后了。

④limit==col:代表col前N個二進制位都是1，表示N個皇后都已經(jīng)擺放好了，游戲結(jié)束，退出遞歸

⑤limit&(~(col|leftLim|rightLim))：pos是在每一行中能選擇的列

⑥ mostRight=pos&(~pos+1)：取出最右邊的一位

⑦ pos-=mostRight：將最右邊的位置從可選擇的位數(shù)中去除，使當前行不能放置皇后

⑧while(pos!=0) 循環(huán)當前行中能選擇的位置

⑨res+= process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1)：循環(huán)下一層

public static int process2(int limit,int col,int leftLim,int rightLim){//遞歸出口if(limit==col){return 1;}//計算能放的位置：int pos= limit&(~(col|leftLim|rightLim));int mostRight=0;int res=0;//檢驗是否能遞歸while(pos!=0){//找最右的位置mostRight=pos&(~pos+1);pos-=mostRight;res+=  process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1);}return res;

我們對代碼中的幾個點進行解釋說明：

三.機器人走路問題：（從暴力遞歸到動態(tài)規(guī)劃的實踐）

問題要求如下：

1.假設(shè)有排成一行的n個位置記為1-N,N一定大于等于2
2.開始時機器人在m位置上，m一定是1-N中的一個
3.機器人要在規(guī)定的步數(shù)到達指定的終點，計算到達指定終點的路線有多少條
4.如果機器人來到1位置只能往右來到2位置
5.如果機器人來到N位置只能往左來到N-1位置
6.如果機器人在其他位置，則機器人可以往右也可以往左

對于暴力遞歸，實現(xiàn)思路就相對比較簡單：對于當前位置而言，如果位置是1，他只能選擇2，如果在2-N-1的位置，他可以向左和向右走，如果在N位置，只能往N-1的位置走，不斷走，直到剩余步數(shù)為0，判斷是不是要求的位置，然后返回結(jié)果。

我們給出關(guān)于暴力遞歸的代碼：

public int walking(int N,int cur,int rest,int P){//編寫遞歸出口if(rest==0){if(cur==P){return 1;}else {return 0;}}//排除特殊情況，在0位置處：只能往后走if(cur==1){return walking(N, cur+1, rest-1, P);}//在最后一個位置，只能往前走if(cur==N){return walking(N, cur-1, rest-1, P);}//在中間，可以往前往后走return walking(N, cur-1, rest-1, P)+walking(N, cur+1, rest-1, P);}

為什么說這是從暴力遞歸到動態(tài)規(guī)劃的實踐開始呢？我們對此進行解釋：

我們能在暴力遞歸的基礎(chǔ)上修改為動態(tài)規(guī)劃，什么是動態(tài)規(guī)劃呢？是將暴力遞歸中重復計算的過程轉(zhuǎn)化為緩存，從而降低暴力遞歸中重復計算的次數(shù)，轉(zhuǎn)而從相關(guān)緩存中獲取，是一種典型的空間換時間的策略，對于動態(tài)規(guī)劃而言，其實最難的部分是寫出關(guān)于動態(tài)規(guī)劃的轉(zhuǎn)移方程。

對這道題來說，這種動態(tài)規(guī)劃的類型是記憶性搜索：如果這個位置有緩存，就直接返回緩存結(jié)果，否則遞歸。

動態(tài)規(guī)劃的的code如下：

public int walkCache(int N,int cur,int rest ,int [][]dp,int P){if(dp[cur][rest]!=-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]=walkCache(N, cur+1, rest-1, dp,P);return dp[cur][rest];}if(cur==N){dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P);return dp[cur][rest];}return dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P)+walkCache(N, cur+1, rest-1,dp, P);}}

四.零和博弈問題：

問題描述：

思路：對于A而言，作為先手，他一定在縱觀全局后選擇對自己最有利的計劃，而B作為后手，只能在A 選擇之后在此基礎(chǔ)上選擇對自己最友好的計劃和策略，換句話說，B選擇的只能是A選擇剩下的。

所以我們需要設(shè)計兩個函數(shù)，一個是先手函數(shù)，選擇其中相對自己而言最優(yōu)的策略，即為選擇自己能選的棋中的最大值，而同樣需要設(shè)計一個后手函數(shù)，它的作用是：在后手參與下選擇相對較小的選擇（只能選擇A選剩下的）

我們給出code：

package violencerecursion;/*** @author tongchen* @create 2023-03-21 16:09*/
public class GameWin {public static void main(String[] args) {GameWin gameWin = new GameWin();int[]arr={1,100,1};System.out.println(gameWin.win(arr));}public int win(int[]arr){//零和博弈問題，解題思路：先手的人拿最優(yōu)的選擇，后手的人只能被迫接收最差的結(jié)果int left=0;int right= arr.length-1;return Math.max(f(arr, 0, arr.length-1),s(arr, 0, arr.length-1));}private int f(int[] arr, int left, int right) {//遞歸出口if(left==right){return arr[left];}//選擇已知策略中最優(yōu)的選擇return Math.max(arr[left]+s(arr,left+1,right),arr[right]+s(arr,left,right-1));}private int s(int[] arr, int left, int right) {if(right==left){return 0;}//B相當于從第二個棋子先選擇（因為第一個棋子肯定被A選走了，B先手選第二個棋子）//但是這種情況下B只能選擇在A縱觀全局后選擇最優(yōu)策略之后被迫選擇劣的選擇（即最小值）return Math.min(f(arr, left+1, right),f(arr, left, right-1));}
}

后續(xù)會更新關(guān)于動態(tài)規(guī)劃的轉(zhuǎn)移方程的編寫思路過程，希望大家能持續(xù)關(guān)注捏~