8000 2 · zwxalgorithm/leetcode-1@40f3ee9 · GitHub
[go: up one dir, main page]

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit 40f3ee9

Browse files
committed
2
1 parent b6c6b31 commit 40f3ee9

File tree

1 file changed

+29
-1
lines changed

1 file changed

+29
-1
lines changed

MinimumPathSum/MinimumPathSum.cpp

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,4 +22,32 @@ class Solution {
2222
}
2323
return dp[m-1][n-1];
2424
}
25-
};
25+
};
26+
27+
// O(n) space
28+
class Solution {
29+
public:
30+
int minPathSum(vector<vector<int> > &grid) {
31+
if (grid.empty()) {
32+
return 0;
33+
}
34+
int m = grid.size();
35+
int n = grid[0].size();
36+
vector<vector<int>> dp(2, vector<int>(n, 0));
37+
int T1 = 1;
38+
int T2 = 0;
39+
for (int i = 0; i < m; i++) {
40+
T1 ^= 1;
41+
T2 ^= 1;
42+
dp[T2][0] = dp[T1][0] + grid[i][0];
43+
for (int j = 1; j < n; j++) {
44+
if (i == 0) {
45+
dp[T2][j] = dp[T2][j-1] + grid[i][j];
46+
} else {
47+
dp[T2][j] = grid[i][j] + min(dp[T1][j], dp[T2][j-1]);
48+
}
49+
}
50+
}
51+
return dp[T2][n-1];
52+
}
53+
};

0 commit comments

Comments
 (0)
0