问题描述

小红面临一个挑战，他有一系列的整数并且想要挑选出其中的某些数，使得这些数的总和恰好等于一个给定的目标值。每个数只能用一次，小红的目标是找到所需整数数量最少的解决方案。如果没有办法达成目标，他需要得到的回答是“No solution”。

输入格式

题解

​ 这道题目可以看作是一个经典的 0-1 背包问题，其中每个整数可以视为一个物品，该整数的和可以视为物品的价值，我们的目标是恰好填满一个和为 $m$ 的“背包”，同时使得使用的整数数量最少。

定义 $dp[i][j]$ 表示从前 $i$ 个整数中选取一些整数，其总和恰好为 $j$ 时的最小数量。状态转移方程如下：