匹配型背包： 1、属于新型的背包类型， 不能和填满型背包混为一谈。 2、两个for循环必须先枚举容量再枚举物品。为什么？ 答：因为匹配型背包除了匹配的长度要相等，字符也要一一匹配，就是字符要求一一匹配所以区别于填满型背包。 如果像填满型背包一样先枚举物品再枚举容量，有可能出现以下情况： 单词1："aa",单词2："bb"。 如果单词2先来，则无法填满字符串"aabb" 。 如果每个单词只能匹配一次，那么只能把单词当作点，建立有向图，然后求哈密顿路。

#include <bits/stdc++.h>
using namespace std;
char s[210], dc[160][110];
int n, b[160], f[210];
int main()
{
    scanf("%s%d", s + 1, &n);int v=strlen(s + 1);
    for (int i=1;i<=n;i++)scanf("%s", dc[i]), b[i] = strlen(dc[i]);
    memset(f,63,sizeof(f));f[0]=0;
    for (int i= 1; i<=v;i++)
        for (int j=1;j<=n;j++)if(i>=b[j])
            if(strncmp(s + i - b[j] + 1, dc[j], b[j]) == 0)
                f[i]=min(f[i],f[i-b[j]]+1);
    printf("%d\n",f[v]);
    return 0;
}

/*
匹配型背包：
1、属于新型的背包类型， 不能和填满型背包混为一谈。
2、两个for循环必须先枚举容量再枚举物品。为什么？
答：因为匹配型背包除了匹配的长度要相等，字符也要一一匹配，就是字符要求一一匹配所以区别于填满型背包。 
如果像填满型背包一样先枚举物品再枚举容量，有可能出现以下情况：
单词1："aa",单词2："bb"。 如果单词2先来，则无法填满字符串"aabb" 。 
如果每个单词只能匹配一次，那么只能把单词当作点，建立有向图，然后求哈密顿路。
*/
#include <bits/stdc++.h>
using namespace std;
char s[210], dc[160][110];
int n, b[160], f[210];
int main()
{
    scanf("%s%d",s+1,&n);int v=strlen(s + 1);
    for (int i=1;i<=n;i++)scanf("%s", dc[i]), b[i] = strlen(dc[i]);
    memset(f,63,sizeof(f));f[0]=0;
    for (int i= 1; i<=v;i++)
        for (int j=1;j<=n;j++)
            if(i>=b[j])
            {
                if(strncmp(s + i - b[j] + 1, dc[j], b[j]) == 0)
                    f[i]=min(f[i],f[i-b[j]]+1);
            }
    printf("%d\n",f[v]);
    return 0;
}

<br />

<br />