2
我想你們都知道一些在求職面試中給予你的「草莓」問題,你需要計算一個二維陣列的兩個角之間的路徑,你只能向上或向右移動,並且你已經計算出了最大價值路徑。 我有一個完美的工作代碼,它在遞歸,但它的複雜性是很高。 我也解決了這個問題,在「for循環」的解決方案,它在O(n^2)複雜性。 但在這個解決方案中,我只是不知道如何在遞歸解決方案中打印路線。 這是我的代碼(在這裏閱讀很長,所以我想你應該複製,編譯和運行)。 看看遞歸解決方案的結果,BTW - 路徑需要從左下角到右上角 我要打印的路線更好的解決方案以同樣的方式:如何在Java中打印二維數組中的最大值路徑?
public class Alg
{
public static void main(String args[])
{
String[] route = new String[100];
int[][]array = {{4,-2,3,6}
,{9,10,-4,1}
,{-1,2,1,4}
,{0,3,7,-3}};
String[][] route2 = new String[array.length][array[0].length];
int max = recursionAlg(array,array.length-1,0,route);
int max2 = loopAlg(array,array.length-1,0,route2);
System.out.println("The max food in the recursion solution is: "+max);
System.out.println("and the route is: ");
printRouteArray(route);
System.out.println("The max food in the loop solution: "+max2);
System.out.println("The route is: ");
//SHOULD PRINT HERE THE ROUTE
}
public static int loopAlg(int [][] arr,int x, int y, String[][] route)
{
int n=0;
int[][]count = new int[arr.length][arr[0].length];
for(int i = x; i>=0 ; i--)
{
for(int j = 0; j<arr[0].length; j++)
{
if (i==x && j==0) {count[i][j]=arr[i][j];}
else if (i == x) { count[i][j]=count[i][j-1]+arr[i][j];}
else if (j == 0) { count[i][j]=count[i+1][j]+arr[i][j]; }
else{
if (count[i][j-1]>count[i+1][j]) {count[i][j]=count[i][j-1]+arr[i][j];}
else { count[i][j]= count[i+1][j]+arr[i][j];}
}
}
}
return count[0][arr[0].length-1];
}
public static int recursionAlg(int [][] arr, int x, int y,String[] route)
{
return recursionAlg(arr,0,x,y,arr[0].length-1,route,0);
}
public static int recursionAlg(int[][]arr,int count,int x, int y, int max_y, String[] route, int i)
{
if (x == 0 && y == max_y) {return count;}
else if (x == 0) {
route[i]="Right";
return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1);
}
else if (y==max_y){
route[i]="Up";
return recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1);
}
else if (recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1)>recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1))
{
route[i]="Up";
return recursionAlg(arr,count+arr[x-1][y],x-1,y,max_y,route,i+1);
}
else
{
route[i]="Right";
return recursionAlg(arr,count+arr[x][y+1],x,y+1,max_y,route,i+1);
}
}
public static void printRouteArray(String[] arr)
{
int i=0;
while (i<arr.length && (arr[i]=="Up" || arr[i]=="Right"))
{
System.out.print(arr[i]+"-->");
i++;
}
System.out.println("End");
}
}
希望你能幫忙,謝謝!
是的,我認爲這就是我一直在尋找的:)謝謝! – TomG 2013-04-29 18:36:08