# Untitled

unknown
plain_text
3 years ago
2.0 kB
5
Indexable
Never
```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;
}
};```