离散型动态规划经典题目
离散型动态规划是计算机科学中一个重要的研究领域。它主要研究问题的最优解，通过对问题进行建模和分析，找到最优解。离散型动态规划常常应用于复杂的优化问题，如路径规划、图像处理、自然语言处理等。本文将介绍离散型动态规划的一个经典题目，包括其解题思路、算法实现等方面。
问题描述
假设有 $n$ 种面额的硬币，面值分别为 $a_1,a_2,\cdots,a_n$，现在要凑出总面值为 $m$ 的钱，每种面额的硬币有无限个，问最少需要多少枚硬币？
解题思路
这个问题可以使用贪心算法进行求解。首先按从小到大的顺序排列硬币，然后从大到小地选取硬币，直到选取的硬币面值之和大于等于 $m$ 为止。这种方法简单易懂，但并不总能得到最优解。
实际上，这个问题也可以使用动态规划进行求解。设 $f(x)$ 表示凑出总面值为 $x$ 的钱所需的最少硬币数，则有以下转移方程：
$$f(x) = \min\{f(x-a_i)+1\}, \quad 1 \leq i \leq n, a_i \leq x$$
其中 $f(x-a_i)$ 表示凑出总面值为 $x-a_i$ 的钱所需的最少硬币数加上一枚面值为 $a_i$ 的硬币。因为每种硬币有无限个，所以需要加上一枚面值为 $a_i$ 的硬币。
动态规划的时间复杂度为 $O(nm)$，其中 $n$ 是硬币种类数，$m$ 是总面值。这个算法虽然比贪心算法耗费了更多时间，但是一定能够得到最优解。
算法实现
下面给出动态规划算法的具体实现。
```
#include
#include
#include
using namespace std;
const int INF = 1e9;
const int N = 1e3 + 10;
int n, m;
int a[N], f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = a[i]; j <= m; j ++ )
f[j] = min(f[j], f[j - a[i]] + 1);
if (f[m] == INF) cout << -1 << endl;
else cout << f[m] << endl;
return 0;
}
```
代码中使用了 `memset` 函数将数组 $f$ 的所有元素初始化为 $+\infty$，这样可以保证所有的 $f(x)$ 都能得到正确的更新。
