问算法:如何从Char数组中找出组合数的最小个数，使其超过目标个数？

EN

因为不允许重复的数字，所以首先要做的就是从数组中删除重复的数字。另外，对数组进行排序也是一个好主意。

如果目标具有d数字，则解决方案也可以是d-digit号码或d+1-digit号码。如果它是一个d+1数字，那么它是您可以从数组值构造的最小数。这部分非常简单：

digit[1] = minimum of nonzero array elements
for p = 2 to d+1:
    digit[p] = minimum of array elements not yet taken

如果解决方案是一个d-digit数字，那么它的第一个数字要么等于目标的第一个数字，要么更大。如果它更大，则无论后面的数字是什么，构造的数字都将大于目标数字，因此对于剩余的数字，您可以复制上述情况的一部分。如果解决方案的第一个数字等于目标的第一个数字，则可以将问题简化为使用较小的合格数字数组为d-1-digit目标找到解决方案的问题。然后你就可以重现了。

对于动态编程方法，保持原始数组中的顺序，您可以在前N个字符之后，仅使用1,2,3...N个字符计算出可能的最大数目。然后，对于N+1th位置，可以使用i个字符的最大数量要么和以前一样，要么是使用当前字符扩展了i-1个字符的前一个答案。

一个技巧，如果你不需要保留顺序，就是对原始数组进行排序。

给出1923年的例子

在位置1，你关心的是1。

在位置2，你关心的是19和9。

在位置3，您关心的是192、92和9。

你关心的是1923、923和93年。

进一步评论：http://en.wikipedia.org/wiki/Dynamic_programming上有一篇关于动态编程的文章。其主要思想是解决小问题，然后使用这些解决方案来解决稍微大一些的问题，然后使用这些解决方案……依此类推，直到你找到了你真正想要解决的问题。

在您的例子中，您希望了解如何从1923年获取少量字符，以便生成大量字符。假设您知道如何从192个字符中提取少量字符来构成一个大数字。在这种情况下，1923的最佳解决方案要么是192的最佳解决方案，要么是加上1923结尾的3的解决方案。这是因为，如果你有一个1923年的解决方案，比我所描述的任何一个解决方案都要好，那么你可以通过采用它，或者删除它的最后一个字符，来得到192的更好的解决方案。

当然，一开始你也不知道192的解决方案，所以你必须从一开始，从1的解决方案开始，然后计算出19的最佳解决方案，然后是192，最后是1923的解决方案-这就是我在上面的例子中展示的。

最后，我不能从你的问题中找出9321或932是可能的解决方案。如果是，问题就简单了，但如果你真的想，你可以用同样的方法解决它。只需对1923进行排序，得到9321，然后像求解1923年那样求解它。