上一篇文章中的两道较为简单的题目都是通过 暴力递归 逐步修改成为 动态规划 ，并使用了严格的 dp表依赖 ，相信小伙伴对此有了初步的认识。 本文我们来练习一道 LeetCode 中 Hard 级别，不使用严格的表依赖的题目。 力扣691. 贴纸拼词 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排

作者推荐 【动态规划】【数学】【C++算法】18赛车 本文涉及知识点 状态压缩 动态规划 LeetCode:691 贴纸拼词 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。 返回你需要拼出 target 的最小贴纸数量。如果

目录 一、题目二、题解2.1 方法一：递归尝试2.2方法二：剪枝2.3 方法三：缓存表 一、题目 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则