动态规划应用：最长上升子序列与数字三角形问题解析

"最长上升子序列与数字三角形问题的动态规划解法" 在动态规划领域，"最长上升子序列"(Longest Increasing Subsequence, LIS) 和“数字三角形”的最佳路径问题是两个经典实例，它们都需要通过递推的方式来求解。 1. **最长上升子序列**: - **问题描述**: 给定一个序列 `a1, a2, ..., aN`，我们需要找到一个最长的上升子序列，即序列中满足严格递增条件的子序列。例如，在序列 `(1, 7, 3, 5, 9, 4, 8)` 中，最长上升子序列有多个，其中一个为 `(1, 3, 5, 8)`，其长度为4。 - **动态规划解法**: 设 `dp[i]` 为序列中前 `i` 项的最长上升子序列的长度，初始状态 `dp[0] = 1`（空序列）。对于每个 `ai`，有两种情况：如果 `ai` 大于 `ai-1`，那么 `dp[i] = dp[i-1] + 1`；否则，`dp[i]` 取 `dp[i-1]` 和 `dp[j] + 1` 的较大值，其中 `j` 是序列中最后一个满足 `aj < ai` 的索引。这样，遍历整个序列后，`dp[N]` 就是所求的最长上升子序列长度。 2. **数字三角形**: - **问题描述**: 数字三角形是一个二维数组，从顶部到底部，每一步只能向左或向右移动到下一行相邻的数字。目标是找出一条路径，使得路径经过的数字之和最大。 - **解题思路**: 类似于最长上升子序列，可以使用动态规划的思路来解决。设 `MaxSum(r, j)` 表示到达第 `r` 行第 `j` 列的最大和，`D[r][j]` 是第 `r` 行第 `j` 列的数字。对于任意位置 `(r, j)`，可以取两种策略：向下左走 `D[r+1][j]` 或者向下右走 `D[r+1][j+1]`，选择两者中和更大的那一条路径。递归公式为 `MaxSum(r, j) = max(MaxSum(r+1, j), MaxSum(r+1, j+1)) + D[r][j]`。 3. **参考程序I**: - 提供的参考程序是一个用C语言实现的数字三角形问题的解决方案。程序定义了一个二维数组 `D` 存储数字三角形，使用递归函数 `MaxSum` 来计算从顶部到底部的最大和。`MaxSum` 函数根据当前行和列，递归地计算下一行的两个相邻位置的最大和，然后返回较大的那个加上当前位置的数值。 动态规划是一种强大的算法思想，它通过存储中间状态来避免重复计算，有效地解决了这两类问题。理解并熟练掌握动态规划，对于解决其他类似问题具有很大的帮助。