离散型动态规划经典题目

离散型动态规划是计算机科学中一个重要的研究领域。它主要研究问题的最优解，通过对问题进行建模和分析，找到最优解。离散型动态规划常常应用于复杂的优化问题，如路径规划、图像处理、自然语言处理等。本文将介绍离散型动态规划的一个经典题目，包括其解题思路、算法实现等方面。

问题描述

假设有 $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)$ 都能得到正确的更新。