public void setDataMatrix(int[][] dataMatrix){ this.dataMatrix = dataMatrix; this.matrixN = dataMatrix.length; this.matrixM = dataMatrix[0].length; this.currentMaxValueArray = new int[matrixM]; this.pathIndexLogArray = new int[matrixN]; }
public void findPath(){ for(int i=0; i<matrixN; i++){ updateCurrentMaxValueArray(i); } int maxElementIndex = findIndexOfMaxValueInArray( currentMaxValueArray ); int maxElementValue = currentMaxValueArray[maxElementIndex]; System.out.println("total max value is: "+maxElementValue); printPath();
赋初值dp[0][0] = 0, ... , dp[0][6] = 2
对于dp[i][j]，可以从五个方向进行扩展
对于每一层，7个数都进行一次扩展，得到下一层的dp，这样从上而下递推，退到第6层，求出min{dp[5][0], ..., dp[5][6]}
给个思路……
for (int row = N-1;row>=0;row--）
计算 row 行所有列到row+1行的最佳路径，并保存每一列的最大值和最佳路径，下一次循环时直接根据从这一行每一列保存的最大值和最佳路径计算。
/**
* 人
↙ ↙ ↓ ↘ ↘
{ 0, -1, 3, 4, 12, 4, 2 },
{ -1, 7, 4, 0, 7, -5, 6 },
{ 5, 3, 4, 0, 0, -2, 7 },
{ 6, 0, -1, -2, 3, 6, 8 }，
{ 4, -5, 6, 7, 0, 0, 2 },
{ 16, 4, 3, 12, 6, 0, 3 } 假设有这样一个数组，人从数组上方开始往下走，此人可以按箭头指的5个方向前进，每走一个格必须取此格的数，要求找到一条从头走到底的路径，使得所取的数相加的和最大。。 */
public static int[][] DATA = {{ 0, 0, 0, 0, 0, 0, 0},
{ 0, -1, 3, 4, 12, 4, 2 },
{ -1, 7, 4, 0, 7, -5, 6 },
{ 5, 3, 4, 0, 0, -2, 7 },
{ 6, 0, -1, -2, 3, 6, 8 },
{ 4, -5, 6, 7, 0, 0, 2 },
{ 16, 4, 3, 12, 6, 0, 3 } };
public static int[][] A = new int[7][7];
public static int X_END = 7;
public static int Y_END = 7;
public static int f(int x, int y){
if(x == X_END - 1){
A[x][y] = DATA[x][y];
return DATA[x][y];
}
//下面进行5个方向的处理
if(y - 2 >= 0){//(x+1,y-2)
int temp;
if(A[x+1][y-2] > Integer.MIN_VALUE){//中间结果已经存在,不用再去计算了
temp = A[x+1][y-2];
}
else{
temp = f(x+1, y-2);
}
if(temp + DATA[x][y] > A[x][y])
A[x][y] = temp + DATA[x][y];
}
if(y - 1 >= 0){//(x+1,y-1)
int temp;
if(A[x+1][y-1] > Integer.MIN_VALUE){//中间结果已经存在,不用再去计算了
temp = A[x+1][y-1];
}
else{
temp = f(x+1, y-1);
} if(temp + DATA[x][y] > A[x][y])
A[x][y] = temp + DATA[x][y];
}
if(y < Y_END){//(x+1,y)
int temp;
if(A[x+1][y] > Integer.MIN_VALUE){//中间结果已经存在,不用再去计算了
temp = A[x+1][y];
}
else{
temp = f(x+1, y);
} if(temp + DATA[x][y] > A[x][y])
A[x][y] = temp + DATA[x][y];
} if(y + 1 < Y_END){//(x+1,y+1)
int temp;
if(A[x+1][y+1] > Integer.MIN_VALUE){//中间结果已经存在,不用再去计算了
temp = A[x+1][y+1];
}
else{
temp = f(x+1, y+1);
} if(temp + DATA[x][y] > A[x][y])
A[x][y] = temp + DATA[x][y];
}
if(y + 2 < Y_END){//(x+1,y+2)
int temp;
if(A[x+1][y+2] > Integer.MIN_VALUE){//中间结果已经存在,不用再去计算了
temp = A[x+1][y+2];
}
else{
temp = f(x+1, y+2);
} if(temp + DATA[x][y] > A[x][y])
A[x][y] = temp + DATA[x][y];
} return A[x][y];
}
public static void findPath(int sum, int x, int y){
if(sum != A[x][y])
return;
System.out.println("(" + x + "," + y + "): " + DATA[x][y]);
if(sum == 0)return;
if(x == X_END - 1)return;
if(y - 2 >= 0 && (sum == DATA[x][y] + A[x+1][y-2])){//(x+1,y-2)
findPath(sum-DATA[x][y], x+1, y-2);
}
else if(y - 1 >= 0 && (sum == DATA[x][y] + A[x+1][y-1])){//(x+1,y-1)
findPath(sum-DATA[x][y], x+1, y-1);
}
else if(y < Y_END && (sum == DATA[x][y] + A[x+1][y])){//(x+1,y)
findPath(sum-DATA[x][y], x+1, y);
}
else if(y + 1 < Y_END && (sum == DATA[x][y] + A[x+1][y+1])){//(x+1,y+1)
findPath(sum-DATA[x][y], x+1, y+1);
}
else if(y + 2 < Y_END && (sum == DATA[x][y] + A[x+1][y+2])){//(x+1,y+2)
findPath(sum-DATA[x][y], x+1, y+2);
}
}
public static void main(String[] args) {
for(int i = 0; i < 7; i++){
for(int j = 0; j < 7; j++){
A[i][j] = Integer.MIN_VALUE;
}
}
int max = f(0, 3);
System.out.println(max);
System.out.println("PATH:");
findPath(max, 0, 3);
}
}结果:
51
PATH:
(0,3): 0
(1,4): 12
(2,4): 7
(3,2): 4
(4,0): 6
(5,2): 6
(6,0): 16
public class DATest {
final static int MIN = -9999;
int[][] dataMatrix = {{ 0, 0, 0, 0, 0, 0, 0},
{ 0, -1, 3, 4, 12, 4, 2 },
{ -1, 7, 4, 0, 7, -5, 6 },
{ 5, 3, 4, 0, 0, -2, 7 },
{ 6, 0, -1, -2, 3, 6, 8 },
{ 4, -5, 6, 7, 0, 0, 2 },
{ 16, 4, 3, 12, 6, 0, 3 } };
int matrixN = dataMatrix.length;//N表示行数
int matrixM = dataMatrix[0].length;//M表示列数
int[] currentMaxValueArray = new int[matrixM];
int[] pathIndexLogArray = new int[matrixN];
public void setDataMatrix(int[][] dataMatrix){
this.dataMatrix = dataMatrix;
this.matrixN = dataMatrix.length;
this.matrixM = dataMatrix[0].length;
this.currentMaxValueArray = new int[matrixM];
this.pathIndexLogArray = new int[matrixN];
}
public void findPath(){
for(int i=0; i<matrixN; i++){
updateCurrentMaxValueArray(i);
}
int maxElementIndex = findIndexOfMaxValueInArray( currentMaxValueArray );
int maxElementValue = currentMaxValueArray[maxElementIndex];
System.out.println("total max value is: "+maxElementValue);
printPath();
}
private void updateCurrentMaxValueArray(int rowIndexNow){
int maxElementIndex = findIndexOfMaxValueInArray( currentMaxValueArray );
int maxElementValue = currentMaxValueArray[maxElementIndex];
for(int i=0; i<matrixM; i++){//all element add this value
currentMaxValueArray[i] = dataMatrix[rowIndexNow][i] + maxElementValue;
}
updatePathIndexLogArray(rowIndexNow, findIndexOfMaxValueInArray(currentMaxValueArray) );
}
private void updatePathIndexLogArray(int rowIndexNow, int pathIndex){
pathIndexLogArray[rowIndexNow] = pathIndex;
}
private int findIndexOfMaxValueInArray(int[] srcArray ){
int tempValue = MIN,returnIndex=0;
for(int i=0; i<srcArray.length; i++){
if(srcArray[i] > tempValue){
tempValue = srcArray[i];
returnIndex = i;
}
}
return returnIndex;
}
private void printPath(){
for(int pathindex : pathIndexLogArray){
System.out.print( pathindex+",");
}
}
public static void main(String[] args) {
DATest test = new DATest();
test.findPath();
}
}
如果没有路径5个选择的限制，到达i+1，j的最长路径和只和第i行中的路径和中的最大者有关，maxsum[i+1][j]=max( maxsum[i][*] ) + data[i+1][j].
如果有5条路径选择的限制，也只需要改动为maxsum[i+1][j]=max( maxsum[i][能够到达该处的列] ) + data[i+1][j].
10楼可以看一下这条路径 4 2 0 0 2 0 她的和是52