动态规划解题：三角数塔与硬币问题

"动态规划经典问题包括三角数塔问题和硬币问题。三角数塔问题要求找到从顶点出发的最大路径和，而硬币问题则涉及找到面值总和为S时，硬币数量的最小值和最大值。" 在动态规划领域，这两个问题都是典型的例子，它们展示了如何通过构建状态转移方程来解决问题。 1. 三角数塔问题： 这个问题的目标是从一个三角形结构中找到一条路径，使得路径经过的数字之和最大。动态规划在这里的作用是通过构建一个二维数组`d`来存储到达每个位置的最大路径和。数组`d`的每个元素表示到达对应位置的最大路径和。从最底层向上回溯，对于每个位置`(i, j)`，我们可以通过比较左右两侧的位置`(i+1, j)`和`(i+1, j+1)`的最大值来更新`d[i][j]`的值。这里，`fnRecursive`函数使用递归方式解决，而`fnMemorySearch`则采用了记忆化搜索优化，避免了重复计算。 ```c int fnMemorySearch(int i, int j) { if (d[i][j] >= 0) return d[i][j]; if (i == n) return (d[i][j] = a[i][j]); d[i][j] = a[i][j] + max(fnMemorySearch(i + 1, j), fnMemorySearch(i + 1, j + 1)); return d[i][j]; } ``` 2. 硬币问题： 这个问题旨在找出给定面值的硬币组合，使得总面值达到S时，硬币数量的最小值和最大值。动态规划的解法是使用两个数组`min`和`max`，分别存储达到每个面值时所需的最小硬币数和最大硬币数。从面值0开始，通过迭代逐步增加面值，并根据当前面值和已有的硬币种类进行计算。对于每个面值S，我们可以选择不使用任何硬币（最小值为0）或者尽可能多地使用硬币（最大值为S/Vk+1，其中Vk是小于S的最大的硬币面值）。 ```c void dp(int *min, int *max) { for (int i = 1; i <= S; i++) { min[i] = max[i] = INF; for (int k = 1; k <= n && V[k] <= i; k++) { min[i] = min(min[i], min[i - V[k]] + 1); max[i] = max(max[i], max[i - V[k]] + 1); } } } ``` 动态规划的核心思想是将复杂问题分解为更小的子问题，并利用子问题的解来构建原问题的解。在这两个问题中，我们通过存储之前计算过的子问题结果，避免了重复计算，从而提高了算法效率。在实际应用中，动态规划常用于解决最优化问题，例如旅行商问题、背包问题等，具有广泛的应用价值。