数组中数字相加 ，和为m ，用最少的数字个数。数组的每个数字可以取得无限个

Question

数组中数字相加 ，和为m ，用最少的数字个数。数组的每个数字可以取得无限个

Answer 1

该回答引用ChatGPT

这是一个经典的动态规划问题，可以使用一个一维数组来记录每个和的最小数字个数。

具体地，假设数组为nums，要求的和为m，我们定义一个一维数组dp，其中dp[i]表示和为i时所需的最小数字个数。

接下来，我们可以使用一个循环来遍历从1到m的每一个和。对于每个和i，我们可以使用另一个循环来遍历数组nums中的每个数字j，如果当前数字j小于等于i且dp[i-j]存在（即和为i-j的情况可以被满足），则我们可以更新dp[i]的值为dp[i-j]+1。这里加1是因为我们选择了一个数字j，所以总的数字个数要加1。

最后，当循环结束后，dp[m]就是所求的结果，即和为m时所需的最小数字个数。

下面是该问题的具体实现代码：

def min_num_of_nums(nums, m):
    dp = [float('inf')] * (m+1)
    dp[0] = 0
    
    for i in range(1, m+1):
        for j in nums:
            if j <= i and dp[i-j] != float('inf'):
                dp[i] = min(dp[i], dp[i-j]+1)
                
    return dp[m]

时间复杂度为O(mn)，其中n为数组nums的长度。