题目难度：二星
考察点：动态规划

方法1：暴力

1. 分析：

这道题类似于完全背包问题，每个货物都可以无限使用，但是要求背包必须装满，而且要求背包中的物品数目最少。由于货物是无限的，那么假设dp[n]表示背包容量为n的能够装满的最少货物个数，如果选择3, 5, 7任意的一种货物重量，那么dp[n-3]、dp[n-5]、dp[n-7]就会是背包容量为n的一种选择，所以问题就转化为了求dp[n-x]，其中x=3、5、7，那么这就是一个递归求解的问题。
举个例子：n=8,求dp[8]
那么dp[8] = min(dp[8-3], dp[8-5], dp[8-7]) + 1 = min(dp[5], dp[3], dp[1]) + 1
其中dp[5] = min(dp[5-3], dp[5-5]) + 1 = min(dp[2], dp[0]) + 1 = 1
其中dp[3] = dp[3-3] + 1 = dp[0] + 1 = 1
在递归回去得到dp[8] = min(1, 1, INF) + 1 = 2,所以dp[8] = 2

2. 复杂度分析：

时间复杂度：O(n^3)
空间复杂度：O(1)


3. 代码： 

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int dfs(int x) {
 if(x == 0) return 0;
 if(x < 0) return INF;
 int ans = INF;
 ans = min(dfs(x-3), min(dfs(x-5), dfs(x-7)))+1;
 return ans;
}
int main() {
 int n;  cin>>n;
 int ans = dfs(n);
 cout<<(ans>=INF?-1:ans)<<endl;
 return 0;
}

方法2：动态规划

1. 分析：

由于上述递归的复杂度太高，我们可以采用动态规划的算法来进行考虑，即把上述的递归改成递推，递推方程已经在上述的方法中列出来了，即dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1，所以直接进行计算，最后输出dp[n]即可。

算法实现：
(1). 输入背包容量n
(2). 预处理dp数组为最大值
(3). 预处理i=3,5,,6,7的时候dp[i]的值,即 dp[3] = dp[5] = dp[7] = 1， dp[6] = 2;
(4). 根据递推方程进行遍历求解，最后输出结果dp[n]

2. 复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)


3. 代码： 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
int dp[MAXN];
int main() {
 int n; cin>>n;
 for(int i=1; i<=n; i++) dp[i] = n+1;
 dp[3] = dp[5] = dp[7] = 1;
 dp[6] = 2;
 for(int i=8; i<=n; i++) dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1;
 cout<<(dp[n]==n+1?-1:dp[n])<<endl;
 return 0;
}