塔子哥面临一个挑战,他有一系列的整数并且想要挑选出其中的某些数,使得这些数的总和恰好等于一个给定的目标值。每个数只能用一次,塔子哥的目标是找到所需整数数量最少的解决方案。如果没有办法达成目标,他需要得到的回答是“No solution”。
这道题目可以看作是一个经典的 0-1 背包问题,其中每个整数可以视为一个物品,该整数的和可以视为物品的价值,我们的目标是恰好填满一个和为 m 的“背包”,同时使得使用的整数数量最少。
定义 dp[i][j] 表示从前 i 个整数中选取一些整数,其总和恰好为 j 时的最小数量。状态转移方程如下:
$$dp[i][j] = \begin{cases} dp[i-1][j], & \text{如果不选择} \ a[i] \\$$