leetcode2310. The one digit number is the sum of integers of K (medium, weekly)

Method 1 ： Completely backpack
At the end of the inclusion is k In the array , Each element can be selected multiple times , And for num Minimum number of

class Solution {
    
public:
    int minimumNumbers(int num, int k) {
    
        
        if (k % 2 == 0 && (num & 1)) return -1;
        if (num == 0) return 0;
        vector<int> coins;
        for (int i = 1; i <= num; ++i) {
    
            if (i % 10 == k) coins.push_back(i);
        }
        int n = coins.size();
        vector<int> dp(num + 1, num + 1);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
    
            for (int j = coins[i]; j <= num; ++j) {
    
                dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
        return dp[num] == num + 1 ? -1 : dp[num];
    }
};

Method 2 ： Consider single digits -> Mathematical problems
Specific ideas ：i The minimum number is 1, At most num,num Only 3000, So try enumerating
Suppose each element
x= 10m+k
That is to find the smallest i bring num=10m’+ik establish , namely ： Traverse i, bring (num-i k)%10==0 , Find it return i

class Solution {
    
public:
    int minimumNumbers(int num, int k) {
    
    
        if (!num) return 0;
        for (int i = 1; i <= num && num - i * k >= 0; ++i) {
    
            if ((num - i * k) % 10 == 0) return i;
        }
        return -1;
    }
};