Untitled

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];
    }
};