# DP + DFS, but get TLE problem, help improve my algorithm

• I use the DFS search for each char in the char array and add dynamic programming method to decrease the program times. But I still get the time limit errors when passing test cases. Who can help me improve my algorithm? Very thanks!

``````public class Solution {

public char[][] dp;
public int xlimit;
public int ylimit;

public ArrayList<Integer> dfs;

public char search(char[][] board, int index_x, int index_y){

int number = index_x * ylimit + index_y;

if(dp[index_x][index_y] != 'N'){
return dp[index_x][index_y];
}

if(index_x == 0 || index_x == xlimit - 1){
dp[index_x][index_y] = board[index_x][index_y];
return board[index_x][index_y];
}
if(index_y == 0 || index_y == ylimit - 1){
dp[index_x][index_y] = board[index_x][index_y];
return board[index_x][index_y];
}
else{
int number1 = (index_x - 1) * ylimit + index_y;
if(!dfs.contains(number1)){
if(dp[index_x-1][index_y] == 'O')
return 'O';
if(search(board, index_x - 1, index_y) == 'O'){
dp[index_x][index_y] = 'O';
return 'O';
}
}

int number2 = (index_x + 1) * ylimit + index_y;
if(!dfs.contains(number2)){
if(dp[index_x+1][index_y] == 'O')
return 'O';
if(search(board, index_x + 1, index_y) == 'O'){
dp[index_x][index_y] = 'O';
return 'O';
}
}

int number3 = index_x * ylimit  + index_y - 1;
if(!dfs.contains(number3)){
if(dp[index_x][index_y - 1] == 'O')
return 'O';
if(search(board, index_x, index_y - 1) == 'O'){
dp[index_x][index_y] = 'O';
return 'O';
}
}

int number4 = index_x * ylimit  + index_y + 1;
if(!dfs.contains(number4)){
if(dp[index_x][index_y + 1] == 'O')
return 'O';
if(search(board, index_x, index_y + 1) == 'O'){
dp[index_x][index_y] = 'O';
return 'O';
}
}
dp[index_x][index_y] = 'X';
return 'X';
}
}

public void solve(char[][] board) {

if(board.length == 0 || board.length == 1)
return;
if(board[0].length == 1)
return;

xlimit = board.length;
ylimit = board[0].length;
dp = new char[xlimit][ylimit];

for(int i=0; i<xlimit; i++){
for(int j=0; j<ylimit; j++){
if(board[i][j] == 'X')
dp[i][j] = 'X';
else
dp[i][j] = 'N';
}
}

for(int i=0; i<xlimit; i++){
for(int j=0; j<ylimit; j++){

if(board[i][j] == 'O'){

if(dp[i][j] == 'X')
board[i][j] = 'X';
else if(dp[i][j] == 'N'){
dfs = new ArrayList<Integer>();
board[i][j] = search(board, i, j);
}
}
else
continue;

}
}

return;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.