【kuangbin带你飞-区间DP-6】H-String painter HDU – 2476

题目链接

题意

给两个长度相等的字符串a,b。
现在有一把刷子，能把字符串中一段区间刷成相同的字母。
现在问你，要把字符串a刷成字符串b，最少需要刷多少次。

思路

关于区间的，很大程度上就是区间dp，这道题的思路看过大神们的题解之后，感觉还是很巧妙的。

1. 使用两次dp，第一次是求目标字符串b在一个空的等长字符串中生成自己的最少刷的次数。第二次是，进行比较，从字符串a到字符串b的过程。
2. 第一次dp，dp[i][j]表示在区间【i,j】中刷出目标字符串对应区间的最少次数，这里使用的是区间左端点拓展的方法，同时使用已经计算过的区间[i+1,j]中的某个点k，来更新dp[i][j]的值。
   状态方程为

   dp[i][j]=min(dp[i+1][k]+dp[k+1][j]) if b[i]==b[k] ,i+1<=k<=j

   每个dp[i][j]初始值是1+dp[i+1][j] 表示当前拓展的b[i]不和区间【i+1,j】一起刷，单独刷他一个。

3. 第二次dp是进行比较，用ans[i]表示刷到字符串a前i个字符后，最少的操作次数。
   状态方程

   ans[i]=ans[j]+dp[j+1[k] if( a[i]!=b[i]) else ans[i]=ans[i-1]

   当前字符不用刷

4. 一些抽象的做题点：

   左端点拓展

   ，

   中间状态的化难到易

   ，

   两种状态的刷

   。

代码

#include<bits/stdc++.h>using namespace std;const int maxn = 105;const int inf = 0x3f3f3f3f;int dp[maxn][maxn];int ans[maxn];int main() {ios::sync_with_stdio(false);string s, t;while(cin >> s) {cin >> t;int n = t.size();memset(dp, 0, sizeof(dp));for(int l = 1; l <= n; l++) {for(int i = 0; i + l <= n; i++) {int j = i + l - 1;dp[i][j] = 1 + dp[i + 1][j];for(int k = i + 1; k <= j; k++) {if(t[i] == t[k]) {dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);}}}}for(int i = 0; i < n; i++)ans[i] = dp[0][i];for(int i = 0; i < n; i++) {if(s[i] == t[i])ans[i] = min(ans[i], ans[i - 1]);else {for(int j = 0; j < i; j++) {ans[i] = min(ans[i], ans[j] + dp[j + 1][i]);}}}cout << ans[n - 1] << endl;}}