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

problem link geeksforgeeks

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 license header, choose License Headers in Project Properties.
     * To change this template file, choose Tools | Templates
     * and open the template in the editor.
 */
package geeksforgeeks;

import java.util.LinkedList;
import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
public class MinimumCostPathUsingBFSUsingLinkedListAsQueue {

    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) {
        LinkedList<Integer> queue = new LinkedList();
        queue.add(0);
        queue.add(0);
        queue.add(0);
        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;
                    queue.add(x + 1);
                    queue.add(y);
                    //             queue.add(cost+data[x+1][y]);
                    //was not able to add this line due to exception
                    queue.add(newCost);

                    queue.add(x - 1);
                    queue.add(y);
                    //queue.add(cost+data[x-1][y]);
                    queue.add(newCost);

                    queue.add(x);
                    queue.add(y + 1);
                    //queue.add(cost+data[x][y+1]);
                    queue.add(newCost);

                    queue.add(x);
                    queue.add(y - 1);
                    //queue.add(cost+data[x][y-1]);
                    queue.add(newCost);

                }

            }
        }
    }
}

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 :slight_smile:

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! :slight_smile: