区间涂色问题

wujw11world / 2023-05-03 / 原文

一眼区间dp
设dp[i][j]为涂完i到j所需的最小次数
当a[i]==a[j]时，dp[i][j] = min(dp[i+1][j-1]+1,min(dp[i+1][j],dp[i][j-1]));
为什么是dp[i+1][j-1]+1,此时会产生一个异想天开的想法，就是取遍历一遍i+1到j-1这一段字符串，看是否有a[i]字符的出现，如果出现的话dp[i][j] = dp[i+1][j-1]，就是上来先把i到j这一段全涂成a[i]，然后去涂其他的，但这种做法不能保证在dp[i+1][j-1]-1的次数内正确涂满其余没涂的，例如，ABABA，dp[2][4] = 3,如果按照以上方法更新，dp[1][5] = 3,实际上dp[1][5] = 4。再来看dp[i][j-1]与dp[i+1][j]，在涂a[i]或a[j]时直接把i-j涂完，不会像前面一样影响答案。
当a[i]！=a[j]时，拆分区间就好

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n;
char a[55];
int dp[55][55];
int main(){
    string s;
    cin>>s; n = s.length();
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++) {
            dp[i][j] = 51;
        }
    }
    for(int i = 1;i<=s.length();i++){
        a[i] = s[i-1];dp[i][i] = 1;
    }

    for (int i = 1; i  <= n-1; i++) {
		if(a[i]!=a[i+1]) dp[i][i+1] = 2;
        else dp[i][i+1] = 1;
    }
    
    for (int len = 3; len <= n; len++) {
			for (int i = 1; i + len - 1 <= n; i++) {
				int j = i + len - 1;
                if(a[i]==a[j]){
                    dp[i][j] = min(dp[i+1][j-1]+1,min(dp[i+1][j],dp[i][j-1]));
                }
                else{
                    
                    for(int k = i;k<=j-1;k++){
                     //   if(i==1&&j==3){
                   //         cout<<dp[i][k]<<" "<<dp[k+1][j]<<" "<<dp[i][j]<<endl;
                    //    }
                        dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);
                    }
                }
			}
		}
    cout<<dp[1][n];
}