why i am getting tle in dynamic programing min Cost problem in java? Plz help

``````class MinimumCostPathUsingDFSusingRecursion {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int totalCases = s.nextInt();
for (int i = 0; i < totalCases; i++) {
int N = s.nextInt();
int data[][] = new int[N][N];
int dpStorage[][] = new int[N][N];
int sum = 0;
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
data[j][k] = s.nextInt();
sum += data[j][k];
}
}
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
dpStorage[j][k] = sum;
}
}

CalculateMinCoast(data, dpStorage, 0, 0, 0);
System.out.println(dpStorage[data.length - 1][data.length - 1]);
}
}

private static void CalculateMinCoast(int[][] data, int[][] dpStorage, int x, int y, int cost) {
if (x < 0 || y < 0 || x >= data.length || y >= data.length || dpStorage[x][y] <= cost + data[x][y]) {
return;
} else {
dpStorage[x][y] = cost + data[x][y];
int x1 = x + 1;
int y1 = y + 1;
int x2 = x - 1;
int y2 = y - 1;
int newCost = dpStorage[x][y];
CalculateMinCoast(data, dpStorage, x, y1, newCost);
CalculateMinCoast(data, dpStorage, x1, y, newCost);
CalculateMinCoast(data, dpStorage, x, y2, newCost);
CalculateMinCoast(data, dpStorage, x2, y, newCost);

}

}
}
``````

please can anyOne tell me what is time complexity of my program … even i done memorisation (dynamic programing) in my program in my own way… but still giving TLE error.
similarly when tried to solve above problem using BFS along with memorisation in my own way, it gave me AC answer…

can anyOne tell me what are complexities of my both programs!

``````    /*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package geeksforgeeks;

import java.util.Scanner;

/**
*
* @author Hemant Dhanuka
*/

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int totalCases = s.nextInt();
for (int i = 0; i < totalCases; i++) {
int N = s.nextInt();
int data[][] = new int[N][N];
int dpStorage[][] = new int[N][N];
int sum = 0;
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
data[j][k] = s.nextInt();
sum += data[j][k];
}
}
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
dpStorage[j][k] = sum;
}
}

CalculateMinCoast(data, dpStorage);
System.out.println(dpStorage[data.length - 1][data.length - 1]);
}
}

private static void CalculateMinCoast(int[][] data, int[][] dpStorage) {
int m = data.length;
while (!queue.isEmpty()) {
int x = queue.pop();
int y = queue.pop();
int cost = queue.pop();

if (x < m && y < m && x >= 0 && y >= 0) {
int newCost = cost + data[x][y];
if (dpStorage[x][y] > newCost) {
dpStorage[x][y] = newCost;
//was not able to add this line due to exception

}

}
}
}
}
``````

In the Q, only 3 moves were allowed. You used 4 in your first solution. Is the Q you are trying to solve a bit different?

1 Like

sorry, that by mistake… link updated

Hey, for some reason, I am inclined to think your first code is more like “From this cell, try all possible paths until a minimum cost path is made or `dpStorage[x][y] <= cost + data[x][y])` is encountered.”

Can somebody please confirm? I will appreciate it!