動态規劃-排成一條線的紙牌博弈等問題

有一個整型數組A，代表數值不同的紙牌排成一條線。玩家a和玩家b依次拿走每張紙牌，規定玩家a先拿，玩家B後拿，但是每個玩家每次隻能拿走最左或最右的紙牌，玩家a和玩家b都絕頂聰明，他們總會采用最優政策。請傳回最後獲勝者的分數。 給定紙牌序列A及序列的大小n，請傳回最後分數較高者得分數(相同則傳回任意一個分數)。保證A中的元素均小于等于1000。且A的大小小于等于300。 測試樣例： [1,2,100,4],4 傳回：101 用暴力遞歸的方法：

定義遞歸函數f(i,j),表示如果arr[i...j]這個排列上的紙牌被絕頂聰明的人拿走，最終能夠獲得什麼分數。

定義遞歸函數s(i,j),表示如果a[i..j]這個排列上的紙牌被絕頂聰明的人後拿，最終能獲得什麼分數。 首先來分析，具體過程如下： 1.如果i==j(隻有一張紙牌)，會被先拿紙牌的人拿走，是以傳回arr[i]; 2.如果i!=j,先拿紙牌的人有兩種選擇，要麼拿走arr[i],要麼拿走arr[j]; 如果拿走arr[i],剩下arr[i+1,j]。對于arr[i+1,j]的紙牌，目前玩家成了後拿的人，是以他後續能獲得的分數為s(i+1,j).如果拿走arr[j],那麼剩下arr[i,j-1],目前玩家後續能獲得的分數為s[i,j-1],作為絕頂聰明的人，必然會在兩種決策中選擇最優的。是以傳回max{arr[i]+s[i+1,j],arr[j]+s[i][j-1]} 然後來分析s(i,j): 1.如果i==j,後拿紙牌的人什麼也拿不到，傳回0 2.如果i!=j,玩家的對手會先拿紙牌。對手要麼先拿走a[i],要麼先拿走arr[j],如果對手拿走arr[i],那麼排列剩下arr[i+1,j],如果對手拿走arr[j],剩下arr[i,j-1],對手也是絕頂聰明的人，是以也會把最差的情況留給玩家是以傳回min{f(i+1,j),f(i,j-1)} 解法一：public int cardGame(int[] arr, int n) { if(arr==null||n==0){return 0;} return Math.max(f(arr,0,n-1),s(arr,0,n-1)); // write code here }

public int f(int[]arr,int start,int end){ if(start==end){return arr[start];} return Math.max(arr[start]+s(arr,start+1,end),arr[end]+s(arr,start,end-1)); } public int s(int[]arr,int start,int end){ if(start==end){return arr[start];} return Math.min(f(arr,start+1,end),f(arr,start,end-1)); } 解法二：public int cardGame(int[] arr, int n) { if(arr==null||arr.length==0){return 0;} int[][] f=new int[n][n]; int[][] s=new int[n][n]; for(int j=0;j<arr.length;j++){ f[j][j]=arr[j]; for(int i=j-1;i>=0;i--){ f[i][j]=Math.max(arr[j]+ s[i][j-1] ,arr[i]+ s[i+1][j] ); //f[i][j]表示在arr[i...j]區間内目前玩家最大的累加和 s[i][j]=Math.min(f[i+1][j],f[i][j-1]); //s[i][j]表示在arr[i..j]區間内的最小累加和 } } return Math.max(f[0][n-1], s[0][n-1]); }

第一個玩家每次會保證自己是本次和另一個玩家取完最大值後再取剩下的的和最大f[i][j]就記錄最大值即Math.max(arr[j]+ s[i][j-1] ,arr[i]+ s[i+1][j] );

對于另一個玩家來說，會取第一個玩家取完剩下的較大的數，對于第一個玩家來說就是沒取數之前較小的即Math.min(f[i+1][j],f[i][j-1]);

換錢的方法數: 給定數組arr,arr中所有的值都為正數且不重複，每個值代表一種面值的貨币，每種面值的貨币可以使用任意張，在給定一個數組aim代表要找的錢數，求換錢有多少種方法 暴力遞歸的方法。arr[5,10,25,1],aim=1000,分析過程如下： 1.用0張5元的，讓其餘的組成1000， 2.用1張5元的，其餘的組成995 3.用2張5.。。 其餘的又用0張，一張。。。将所有的張數加起來就是最後的結果。 解法一：暴力遞歸法： public int coins(int[] arr,int aim){ if(arr==null||arr.length==0||aim<0){return 0;} return proccess(arr,0,aim); } public int process(int[] arr,int index,int aim){ int res=0;//初始化方法數 if(index==arr.length){res=aim==0?1:0;} else { for(int i=0;arr[index]*i<=aim;i++){ res+=process(arr,index+1,aim-arr[index]*i);//依次遞歸剩下的錢的組成方案數 } } return res; } 解法二：記憶化搜尋： 用一個map數組儲存上一次計算出的中間值，map[i][j]表示遞歸過程p(i,j)的傳回值。 map[i][j]=0,表示遞歸過程未計算過，map[i][j]=-1表示遞歸過程計算過，但結果為0，其他情況時則儲存遞歸過程的值。 public int coins(int[] arr,int aim){ if(arr==null||arr.length==0||aim==0){return 0;} int[][] map=new int[arr.length+1][aim.length+1]; return process(arr,0,aim,map); } public int process(int[] arr,int index,int aim,int[][] map){ int res=0; if(index==arr.length){res=aim==0?1:0;} else{ int mapvalue=0; for(int i=0;arr[index]*i<=aim;i++){ mapvalue=map[index+1][aim-arr[index]*i]; if(mapvalue!=0){res+=mapvalue==-1?0:mapvalue;} else{ res+=process(arr,index+1,aim-arr[index]*i,map); } } } map[index][aim]=res==0?-1:res; return res; } 解法三：生成行數N，列數aim+1的矩陣dp,dp[i][j]的含義是在使用arr[0...i]的貨币的情況下，組成錢數j有多少種方法。 1.對于矩陣dp的第一列dp[...][0],表示組成錢數為0的方法數，一種，很明顯就是不使用任何貨币，是以dp的值為1. 2.對于矩陣dp的第一行的值dp[0][...],表示隻能使用arr[0]的情況下，組成錢的方法數dp[i][k*arr[0]]=1 3.除第一行和第一列的其他位置，dp[i][j]是以下幾個情況的累加和 完全不用arr[i]貨币，剩下的錢用arr[0..i]組成時，方法數為dp[i-1][j] 用一個arr[i]貨币，剩下的錢用arr[0..i]組成，方法數為dp[i-1][j-arr[j]*i] 最終dp[i][j]就是最終結果。 public int coins(int[] arr,int aim){ if(arr==null||arr.length==0||aim<0){return 0;} int[][] dp=new int[arr.length][aim+1]; for(int i=0;i<arr.length;i++){dp[i][0]=1;}//初始化第一行 for(int j=1;j<arr[0]*j<=aim;j++){dp[0][arr[0]*j]=1;} for(int i=1;i<arr.length;i++){ for(int j=1;j<=aim;j++){ //周遊每種情況求結果數 int res=0；//當用arr[0..i]時。組成j的方法數。 dp[i][j]=dp[i-1][j]; dp[i][j]+=j-arr[i]>=0?dp[i][j-arr[i]]:0; } } return dp[arr.length-1][aim]; } 以上方法的時間複雜度O(N*aim),空間複雜度O(aim); 再将空間壓縮，得到空間複雜度O(aim)的算法 public int coins(int[] arr,int aim){ if(arr==null||arr.length==0||aim<0){return 0;} int[] dp=new int[aim+1]; for(int i=0;arr[0]*j<=aim;j++){dp[arr[0]*j]=1;} for(int i=1;i<arr.length;i++){ for(int j=1;j<=aim;j++){dp[i]+=j-arr[i]>=0?dp[j-arr[i]]:0;} } return dp[aim]; } 跳躍遊戲 給定數組arr,arr[i]==k,代表從位置i向右跳躍1~k個距離。比如arr[2]==3,代表從位置2可以跳到位置3，位置4，位置5。如果從位置0出發，傳回最少跳幾次能夠跳到arr最後的位置上。 從左到右周遊arr,假設周遊到位置i, 如果cur大于=i,說明條jump步可以到達位置i， 如果cur小于i,說明不能夠到大位置，需要多跳一步才行 public jump(int[] arr){ if(arr==null||arr.length==0){return 0;} int jump=0; int cur=0; int next=0; for(int i=0;i<arr.length;i++){ if(cur<i){jump++;cur=next;}//可以到達 next=Math.max(next,i+arr[i]);//将next更新，表示下一跳多跳一步到達的最遠位置 } return jump; }