Untitled
unknown
plain_text
4 years ago
2.0 kB
8
Indexable
https://leetcode.com/problems/fibonacci-number/ class Solution { public: int fib(int n) { if (n == 0) { return 0; } long long second_last = 0; long long last = 1; for (int i = 2; i <= n; i++) { long long current = second_last + last; second_last = last; last = current; } return last; } }; 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[2][m]; dp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { dp[1][j] = 1e9; dp[1][j] = min(dp[1][j], dp[0][j] + grid[i][j]); if (j > 0) { dp[1][j] = min(dp[1][j], dp[1][j - 1] + grid[i][j]); } } for (int j = 0; j < m; j++) { dp[0][j] = dp[1][j]; } } return dp[0][m - 1]; } }; https://leetcode.com/problems/longest-valid-parentheses/ class Solution { public: int longestValidParentheses(string s) { int n = s.length(); if (n == 0) { return 0; } int dp[n + 1]; dp[0] = dp[1] = 0; int ans = 0; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i - 2] == '(' && s[i - 1] == ')') { dp[i] = dp[i - 2] + 2; } if (s[i - 2] == ')' && s[i - 1] == ')' && i - dp[i - 1] - 2 >= 0 && s[i - dp[i - 1] - 2] == '(') { dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2; } ans = max(ans, dp[i]); } return ans; } };
Editor is loading...