牛牛与糖题解_牛客博客

本题乍一看像完全背包问题，但是仔细分析可以看出其实是一道bfs。bfs的状态即为当前买的糖数，从0搜索到m。要注意的是超过m的状态需要剪枝，否则容易越界。
时间复杂度为 $O(nm)$
空间复杂度为 $O(n+m)$
以下是AC代码：

#define maxm 10005
class Solution {
public:
    /**
     * 返回最少需要买的糖包数
     * @param n int整型 表示共有多少种糖包
     * @param m int整型 表示一共需要买的糖数
     * @param num int整型一维数组 表示每种糖包所含的糖的数量
     * @param numLen int num数组长度
     * @return int整型
     */
    int solve(int n, int m, int* num, int numLen) {
    int dis[maxm];
    memset(dis,0,sizeof(dis));//初始设置为0，既用来标记，也用来保存答案
    queue<int> q;
    q.push(0);//初始状态为0
    while(!q.empty())
    {
        int t=q.front();
        if(t==m)
            break;
        q.pop();
        for(int i=0;i<n;i++)
        {
            int w=num[i]+t;
            if(w<=m&&!dis[w])//w超过m不予考虑，dis[w]为0表示没有访问过该状态
            {
                dis[w]=dis[t]+1;
                q.push(w);
            }
        }
    }
    return dis[m];
    }
};

另外，暴力也可以做本题，但是本质上和bfs的做法是相同的，并且代码量和bfs相当。
时间复杂度为 $O(nm)$
空间复杂度为 $O(n+m)$

#define maxm 10005
class Solution {
public:
    /**
     * 返回最少需要买的糖包数
     * @param n int整型 表示共有多少种糖包
     * @param m int整型 表示一共需要买的糖数
     * @param num int整型一维数组 表示每种糖包所含的糖的数量
     * @param numLen int num数组长度
     * @return int整型
     */
    int solve(int n, int m, int* num, int numLen) {
    int book[maxm];
    memset(book,0,sizeof(book));
    int ans=0;
    vector<int> vec[maxm];
    vec[0].push_back(0);
    while(!book[m])
    {
        for(int i=0;i<vec[ans].size();i++)
        {
            int u=vec[ans][i];
            for(int j=0;j<n;j++)
            {
                if(u+num[j]<=m&&book[u+num[j]]==0)
                {
                    book[u+num[j]]=1;
                    vec[ans+1].push_back(u+num[j]);
                }
            }
        }
        ans++;
    }
    return ans;
    }
};