# Untitled

unknown
plain_text
3 years ago
2.0 kB
8
Indexable
Never
```https://leetcode.com/problems/minimum-path-sum/
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
if (n == 0) {
return 0;
}
int m = grid[0].size();
if (m == 0) {
return 0;
}
int dp[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = 1e9;
}
}
dp[0][0] = grid[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i > 0) {
dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
}
if (j > 0) {
dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
}
}
}
return dp[n - 1][m - 1];
}
};

https://leetcode.com/problems/generate-parentheses/
class Solution {
public:
vector<string> generateParenthesis(int n) {
set<string> dp[n + 1];
dp[1].insert("()");
for(int i = 2; i <= n; i++) {
for(auto it : dp[i - 1]) {
dp[i].insert("(" + it + ")");
}
for(int j = 1; j < i; j++) {
for(auto it : dp[j]) {
for(auto it1 : dp[i - j]) {
dp[i].insert(it + it1);
}
}
}
}
vector<string> ans;
for(auto it : dp[n]) ans.push_back(it);
return ans;
}
};

https://leetcode.com/problems/decode-ways/
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
int dp[len + 1];
dp[0] = 1;
for(int i = 1; i <= len; i++) {
dp[i] = 0;
if(s[i - 1] != '0') dp[i] += dp[i - 1];
if(i > 1 && s[i - 2] != '0' && (10 * (s[i - 2] - '0') + (s[i - 1] - '0')) <= 26)
dp[i] += dp[i - 2];
}
return dp[len];
}
};```