基于动态规划的方法用于优化拼图问题的设计与实现

文章结构概述

• 课题说明
  • 探讨

题目描述

我们提供了 N 类不同种类的贴纸，每张贴纸上均印有一个小写的英文单词。你的目标是从自身拥有的贴纸集合中，剪下单个字母并重新排列组合，以拼出指定的目标字符串 target。在操作过程中，你可以多次使用同一张贴纸，且每种贴纸的数量被视为无限。请计算拼出目标字符串 target 所需的最少贴纸数目，若无法完成该任务，则返回 -1。

分析

首先设定f(i,j)用于表示获取目标字符串中从i到j下标所构成子串所需贴纸的最小数量。接着，f(i,j)可表示为f(i,k)与f(k,j)之间的最小值（其中i < k < j）。根据上述递推关系式，可以编写相应的程序代码。

    #include <iostream>
    #include <string>
    #include <vector>
    #include <string.h>
    
    using namespace std;
    /***********************************************************************************
    我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。
    
    你希望从自己的贴纸集合中