UnKoder #07 : AB Warp

なんとか完答。
https://www.hackerrank.com/contests/unkoder-07/challenges/ab-warp

問題

A,Bで構成されたN文字の文字列がある。
先頭の文字から初めて、1手で隣接する位置か、同じ文字の位置にワープできる。

最後の文字に到達するので最小何手かかるか。

解法

愚直にDPで最小値を求めるだけ。

実際は同じ文字のうち一番後ろに存在するものか、もしくは次の文字に移動するかの2択なのでO(N)で解けるが、以下は移動先を全部チェックしているのでO(N^2)。

int L;
string S;
int step[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	FOR(i,100) step[i]=1010;
	
	step[0]=0;
	FOR(i,L) {
		step[i+1]=min(step[i+1],step[i]+1);
		for(j=i+1;j<L;j++) if(S[i]==S[j]) step[j]=min(step[j],step[i]+1);
	}
	cout<<step[L-1]<<endl;
}

まとめ

まだウォームアップ。