DynamicProgrammingStriver/MinPathSumLecture10.cpp at main · dhruvkej9/DynamicProgrammingStriver · 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
79
80
81
82
83
84
85
86
87
88
89
#include <vector>
#include <iostream>
using namespace std;
int solve2(int i,int j,vector<vector<int>> &grid,vector<vector<int>> dp)
{
    if(i == 0 && j == 0) return grid[i][j];
    if(i<0 || j<0) return 1e9;
    if(dp[i][j] != -1) return dp[i][j];
    int up = grid[i][j] + solve2(i-1,j,grid,dp);
    int left = grid[i][j] + solve2(i,j-1,grid,dp);
    return dp[i][j] = min(up,left);

}
int solve1(int i,int j,vector<vector<int>> &grid)
{
    if(i == 0 && j == 0) return grid[i][j];
    if(i<0 || j<0) return 1e9;
    int up = grid[i][j] + solve1(i-1,j,grid);
    int left = grid[i][j] + solve1(i,j-1,grid);
    return min(up,left);

}
int solve3(vector<vector<int>> &grid)
{
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<int>> dp(n,vector<int> (m,0));
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            if(i == 0 && j == 0) dp[i][j] = grid[i][j];
            else
            {
                int up = grid[i][j];
                if(i > 0) up += dp[i-1][j];
                else up += 1e9;

                int left = grid[i][j];
                if(j > 0) left += dp[i][j-1];
                else left += 1e9;

                dp[i][j] = min(left,up);
            }
        }
    }
    return dp[n-1][m-1];

}
int solve4(vector<vector<int>> &grid)
{
    int n = grid.size();
    int m = grid[0].size();
    vector<int> prev(m,0);
    for(int i = 0;i < n;i++)
    {
        vector<int> cur(m,0);
        for(int j = 0;j < m;j++)
        {
            if(i == 0 && j == 0) cur[j] = grid[i][j];
            else
            {
                int up = grid[i][j];
                if(i > 0) up += prev[j];
                else up += 1e9;

                int left = grid[i][j];
                if(j > 0) left += cur[j-1];
                else left += 1e9;

                cur[j] = min(left,up);
            }
        }
        prev = cur;
    }
    return prev[m-1];

}
int minSumPath(vector<vector<int>> &grid)
{
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<int>> dp(n,vector<int> (m,-1));
//     return solve1(n-1,m-1,grid);
//     return solve2(n-1,m-1,grid,dp);
//     return solve3(grid);
    return solve4(grid);

}