# CFR 795 I. Composing Of String ( DP )

Problem - I - Codeforces

The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set.
The next n lines contain n non-empty strings consisting of lowercase letters of the English alphabet. The length of each of these strings does not exceed 50 symbols. It is possible that some strings from Stepan's set are the same.
The next line contains the non-empty string s, consisting of lowercase letters of the English alphabet — Stepan's favorite string. The length of this string doesn't exceed 2500 symbols.

dp[ i ] : 已完成 target[ 0, i ) 需要的花費。

O( | target | * N * max( | word[ i ] | )

```using System;
using System.Linq;

public static class Program {
public static void Main() {
int N = Convert.ToInt32( Console.ReadLine() );
string[] word = new string[ N ];
for( int i = 0; i < N; ++i ) {
word[ i ] = Convert.ToString( Console.ReadLine() );
}
string target = Convert.ToString( Console.ReadLine() );
int[] dp = new int[ target.Length + 1 ];
for( int i = 1; i <= target.Length; ++i ) {
dp[ i ] = 0x3f3f3f3f;
}
for( int i = 0; i < target.Length; ++i ) {
for( int j = 0; j < N; ++j ) {
int ptr = i;
for( int k = 0; k < word[ j ].Length && ptr < target.Length; ++k ) {
if( word[ j ][ k ] == target[ ptr ] ) {
++ptr;
}
}
if( dp[ ptr ] > dp[ i ] + 1 ) {
dp[ ptr ] = dp[ i ] + 1;
}
}
}
if( dp[ target.Length ] == 0x3f3f3f3f ) {
Console.WriteLine( -1 );
} else {
Console.WriteLine( dp[ target.Length ] );
}
}
}
```