91)粉刷房子
二维dp
class Solution{
public:
int minCost(vector<vector<int>>& costs){
int n = costs.size();
vector<vector<int>> f(n+1, vector<int>(costs[0].size(), 0));
for(int i=1; i<=n; i++){
for(int j=0; j<costs[0].size(); j++){
f[i][j] = min(f[i-1][(j+1)%3], f[i-1][(j+2)%3]) + costs[i-1][j];
}
}
int res = INT_MAX;
for(int j=0; j<3; j++){
res = min(res, f[n][j]);
}
return res;
}
};
dp优化空间
class Solution{
public:
int minCost(vector<vector<int>>& costs){
int n = costs.size();
int a0 = costs[0][0];
int a1 = costs[0][1];
int a2 = costs[0][2];
for(int i=1; i<n; i++){
int b0 = min(a1, a2)+costs[i][0];
int b1 = min(a0, a2)+costs[i][1];
int b2 = min(a0, a1)+costs[i][2];
a0 = b0;
a1 = b1;
a2 = b2;
}
return min(a0, min(a1, a2));
}
};
92)翻转字符
class Solution{
public:
int minFlipsMonoIncr(string s){
int n = s.size();
vector<int> cnt(n+1, 0);
for(int i=1; i<=n; i++){
cnt[i] = cnt[i-1]+(s[i-1]=='1');
}
int res = INT_MAX;
for(int i=0; i<=n; i++){
res = min(res, cnt[i]+(n-i-cnt[n]+cnt[i]));
}
return res;
}
};
93)最长斐波那契数列
class Solution{
public:
int lenLongestFibSubseq(vector<int>& arr){
vector<vector<int>> dp(arr.size(), vector<int>(arr.size()));
unordered_map<int, int> mp;
for(int i=0; i<arr.size(); i++){
mp[arr[i]] = i;
}
int ret = 0;
for(int i=1; i<arr.size(); i++){
for(int j=0; j<i; j++){
int temp = arr[i] - arr[j];
if(mp.count(temp) && mp[temp]<j){
dp[i][j] = dp[j][mp[temp]]+1;
}else{
dp[i][j] = 2;
}
ret = max(ret, dp[i][j]);
}
}
return ret>2 ? ret : 0;
}
};