一.746. 使用最小花費爬樓梯

FS+記憶化搜索優化:

const int N = 1010;class Solution {
public:int mem[N];int dfs(vector<int>& cost, int x){if(mem[x]) return mem[x];int sum = 0;if(x == 0 || x == 1) return 0;else{sum = min(dfs(cost, x - 1) + cost[x - 1], dfs(cost, x - 2) + cost[x - 2]);}mem[x] = sum;return sum;}int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();int ans = dfs(cost, n);return ans;}
};

?動態規劃:
?

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {const int N = 1010;int n = cost.size();int f[N];for(int i = 2; i <= n; i++){f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);}return f[n];}
};

二.300. 最長遞增子序列

const int N = 2510;class Solution {
public:int mem[N];int dfs(vector<int>& nums, int x){if(mem[x]) return mem[x];int ans = 1;for(int i = 0; i < x; i++){if(nums[i] < nums[x]){ans = max(ans, dfs(nums, i) + 1);}}mem[x] = ans;return ans;}int lengthOfLIS(vector<int>& nums) {int n = nums.size();int ans = INT_MIN;int f[N];// for(int i = 0; i < n; i++){//     ans = max(ans, dfs(nums, i));// }// return ans;    for(int i = 0; i < n; i++){f[i] = 1;for(int j = 0; j < i; j++){if(nums[j] < nums[i]){f[i] = max(f[i], f[j] + 1);}}}return f[n];}
};