Description
TL;DR 粉刷匠
给定一个字符串\(s\)和空串\(t\)，每次操作可以覆盖任意连续长度的字符，但必须是相同字符。求从\(t\)串到\(s\)串的最少操作次数
Constraints
\(s\)长度不超过\(100\)
Solution
区间DP即可
Code
class Solution {
public:
int strangePrinter(string s) {
int dp[103][103];
memset(dp, -1, sizeof dp);
constexpr static int BAD = 1<<20;
auto DP = [&](auto &&DP, int l, int r) -> int {
if(l == r) return 1;
if(l > r) return BAD;
if(~dp[l][r]) return dp[l][r];
int ans = BAD;
if(s[l] == s[r]) ans = min(DP(DP, l+1, r), DP(DP, l, r-1));
for(int p = l; p < r; p++) {
ans = min(ans, DP(DP, l, p) + DP(DP, p+1, r));
}
return dp[l][r] = ans;
};
return DP(DP, 0, s.size() - 1);
}
};