CFR 795 I. Composing Of String ( DP )

Problem - I - Codeforces

題意：
有 N 種字串。你的目標字串為 target。問至少要連接幾次字串，才能使得這個大字串的子序列有 target。

制約：
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 ] );
    }
  }
}