LeetCode Weekly Contest 199 : 1531. String Compression II

数か月ぶりの難易度8。
https://leetcode.com/contest/weekly-contest-199/problems/string-compression-ii/

問題

N文字の文字列Sが与えられる。
ここから最大K文字取り除いたのち、残った文字列をランレングス圧縮するとき、圧縮後の文字列長の最小値を求めよ。

解法

あらかじめ、n文字を圧縮すると何文字になるかテーブルを作っておこう。以下これをf(n)と呼ぶ。

dp(n,k) := n文字目まで圧縮・削除処理を行ったとき、あと削除可能な文字がk文字の時の圧縮後最短文字列長
とする。dp(0,K)=0から初めてdp(N,0)を求めよう。

今dp(i,k)がわかっているとき、

• i+1文字目を削除する: dp(i+1,k-1)=dp(i,k)
• i+1文字目からL文字を残す。ただしそのうち(i+1)文字目と異なる文字がm個あるとき、dp(i+L,k-m)=dp(i,k)+f(L-m)

とテーブルを更新していけばよい。

int len[101];

int dp[102][102];

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int K) {
		int N=s.size();
		
		int i,j,k;
		ZERO(dp);
		FOR(i,101) FOR(j,101) dp[i+1][j]=1<<20;
		
		len[0]=0;
		len[1]=1;
		for(i=2;i<=9;i++) len[i]=2;
		for(i=10;i<=99;i++) len[i]=3;
		len[100]=4;
		
		FOR(i,N) {
			int oth=0;
			for(int l=1;i+l<=N;l++) {
				if(s[i+l-1]!=s[i]) oth++;
				FOR(k,K+1) if(k>=oth) {
					dp[i+l][k-oth]=min(dp[i+l][k-oth],dp[i][k]+len[l-oth]);
				}
			}
			FOR(k,K+1) if(k) dp[i+1][k-1]=min(dp[i+1][k-1],dp[i][k]);
		}
		
		
		return dp[N][0];
        
    }
};

まとめ

最初別解法に行ってしまいサンプルが合わずタイムロス。