leetcode2310. 个位数字为 K 的整数之和(中等，周赛)

方法一：完全背包
在包含结尾是k的数组中，每个元素可选多次，和为num的最少个数

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];
    }
};

方法二：考虑个位数->数学问题
具体思路：i最少个数为1，最多为num，num只有3000，因此可以试着枚举
假设每个元素
x= 10m+k
即找到最小的i使得num=10m’+ik成立，即：遍历i，使得 (num-i k)%10==0 ，找到即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;
    }
};