Untitled
Dynamic programming Part-1 Unacademyunknown
plain_text
4 years ago
2.0 kB
13
Indexable
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]; } };
Editor is loading...