(Topcoder)TCC algorithm Round 4 Chess Metric

public class ChessMetric {

private static int[] dx=new int[]{1,-1,0,0,1,-1,-1,1,2,-2,2,-2,1,1,-1,-1};
        private static int[] dy=new int[]{0,0,-1,1,1,-1,1,-1,1,1,-1,-1,2,-2,2,-2};
        private static int dp[][];

public static long howMany(int size,int[] start,int[] end,int numMoves){
dp=new int[size][size];
for(int[] row:dp)
Arrays.fill(row, -1);

int x=start[0];
int y=start[1];

int ret=0;
for(int i=0;i<16;i++)
{
ret=Math.max(ret,move(x+dx[i],y+dy[i],end,numMoves));
}
return ret;

}
private static int move(int x,int y,int[] end,int numMoves)
{
if(x<0 || y<0 || x>=dp.length ||y >=dp.length)
return 0;

if(x==end[0] && y==end[1] && numMoves==0)return 1;

if(numMoves<0)return 0;

if(dp[x][y]!=-1)return dp[x][y];

int ret=0;
for(int i=0;i<16;i++){
ret+=move(x+dx[i],y+dy[i],end,numMoves--);
}

return dp[x][y]=ret;
}
}

-->>>동적계획을 하기 위해 선언한 2차 dp[x][y] 문제가 있다. 그래서 dp[x][y][numMoves]로 바꾸었다. 그 이유는 dp[x][y]로하게 되면 총 3번 움직였을 때랑 2번 움직였을 때랑은 엄연히 다르기 때문이다. 동적계획이 잡혀가고있다...


public static long howMany(int size,int[] start,int[] end,int numMoves){

dp=new int[size][size][numMoves+1];
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
for(int k=0;k<numMoves+1;k++)
dp[i][j][k]=-1;

int x=start[0];
int y=start[1];

return move(x,y,end,numMoves);

}
private static int move(int x,int y,int[] end,int numMoves)
{
if(x<0 || y<0 || x>=dp.length ||y >=dp.length)
return 0;
if(x==end[0] && y==end[1] && numMoves==0)return 1;
if(numMoves<0)return 0;
if(dp[x][y][numMoves]!=-1)return dp[x][y][numMoves];

int ret=0;
for(int i=0;i<16;i++){
ret+=move(x+dx[i],y+dy[i],end,numMoves-1);
}

dp[x][y][numMoves]=ret;
return ret;
}

---->>>>>>.다음과 같이 바꾸었다. 또한 numMoves-1을 처음에는 numMoves--로 했는데 계속 에러 발생....... 이는 numMoves--는 일단 numMoves값을 다음 함수에 집어넣은후 -1을 하기 때문이다...주의하자..!!



<KEY 포인트>
동적계획법으로 접근하기 위해서는 배열을 선언하는게 중요하다. x,y,numMoves에 따라서 방문했던 것이 달라지기 때문에 3중배열로 접근해야 한다.