DSA/gridminpath.cpp at main · Saquib504/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;


// int f(int i, int j, vector<vector<int>>&grid, vector<vector<int>>&memo) {
//     if(i == 0 && j == 0) {
//         return memo[i][j] = grid[i][j];
//     }
//     if(i < 0 || j < 0) return INT_MAX;

//     if(memo[i][j] != -1) return memo[i][j];

//     int up = f(i-1, j, grid, memo);
//     int left = f(i, j-1, grid, memo);

//     return memo[i][j] = grid[i][j] + min(up, left);
// }

int countMinPath(vector<vector<int>>&grid) {
    int m = grid.size();
    int n = grid[0].size();

    if(grid[0][0] == -1 || grid[m-1][n-1] == -1) return -1;

    vector<vector<int>>memo(m, vector<int>(n,-1));

    // return f(m-1, n-1, grid, memo);

    //Tabulation Method
//     for(int i = 0; i < m; i++) {
//         for(int j = 0; j < n; j++) {
//             if(i == 0 && j == 0) {
//                 memo[i][j] = grid[i][j];
//                 continue;
//             }

//             int up = INT_MAX;
//             int left = INT_MAX;

//             if(i > 0) up = memo[i-1][j];
//             if(j > 0) left = memo[i][j-1];

//             memo[i][j] = grid[i][j] + min(up, left);
//         }
//     }
//     return memo[m-1][n-1];

    //Space optimization
    vector<int>prev(n, INT_MAX);

    for(int i = 0; i < m; i++) {
        vector<int>temp(n, INT_MAX);
        for(int j = 0; j < n; j++) {
            if(i == 0 && j == 0) {
                temp[j] = grid[i][j];
                continue;
            }

            int up = INT_MAX;
            int left = INT_MAX;

            if(i > 0) up = prev[j];
            if(j > 0) left = temp[j-1];

            temp[j] = grid[i][j] + min(up, left);
        }
        prev = temp;
    }
    return prev[n-1];
}

int main() {
    vector<vector<int>>grid = {{1, 1,1,1,1}, {60,70,60,19,1},{1,1,1,1,1},{1,50,40,20,22}, {1,1,1,1,1}};

    cout << countMinPath(grid) << endl;
    return 0;
}