我想从数组中找到元素的总和等于给定数的最少元素数。
最佳答案
看起来像是一个简单的动态规划任务。
假设数组A中有N个元素，你想求出元素个数最少且总和为S。然后我们可以很容易地解决这个问题，时间复杂度为 O(N x S)。
考虑 dp[i][j] - 前 i 个元素中总和为 j 的最小元素数， 1 <= i <= N 和 0 <= j <= S。然后对于 A[i] <= j <= S:
dp[i][j] = min(无穷大, dp[i - 1, j], 1 + dp[i - 1][j - A[i]])。
我们可以假设 dp[0][0] = 0，dp[0][j] = 无穷大 0 < j <= S .
关于c++如何从 vector 中找到总和为给定数字的元素的最小数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41201825/