动态规划解数字三角形问题

"购物问题-动态规划基础讲解" 在动态规划领域，购物问题是一个经典的问题，它涉及如何在有限的约束条件下最大化收益。在这个特定的购物问题中，ACM商场正在销售若干种商品，并且对购买行为设定了特定的规则：某些商品不能同时购买，而且每种超低价商品限购一件。问题的复杂性在于需要找到一种购买策略，使得顾客能够节省最多的钱。 动态规划是一种解决问题的有效方法，它通过构建子问题并存储解决方案来避免重复计算，从而提高效率。在这个购物问题中，我们可以定义一个状态数组dp[i][j]，表示考虑前i种商品，如果第j种商品被购买时，能够节省的最大金额。然后，我们可以根据所有可能的选择（购买或不购买第j种商品）来更新这个状态。 首先，我们需要初始化dp数组，通常从最简单的情况开始，即只有一种商品时，最大节省金额就是该商品的原价减去折扣价。接着，对于每种商品，我们可以考虑两种情况：购买和不购买。如果购买第j种商品，那么需要满足不与之前已选的商品冲突，此时节省的金额是dp[i-1][k]加上第j种商品的折扣价（其中k是上一步选择的商品，k != j）。如果不购买第j种商品，那么节省的金额就是dp[i-1][j]。然后我们取这两种情况中的较大值作为dp[i][j]的值。 这个问题的难点在于处理商品之间的禁止购买关系。由于题目中提到，不存在连续的商品不能同时购买，因此我们可以通过贪心策略，将商品按照原价排序，优先选择原价高的商品，这样更有可能达到最大节省。 在另一个示例问题“数字三角形”中，目标是找到从数字三角形的顶部到底部的最大路径和。这同样可以使用动态规划解决。我们可以定义一个二维数组dp，其中dp[r][j]表示到达第r行第j列的路径和的最大值。从第r行开始，我们需要选择是向左还是向右走，即dp[r][j] = max(dp[r+1][j], dp[r+1][j+1]) + D[r][j]，其中D[r][j]是数字三角形中第r行第j列的数字。最后，dp[1][1]就是整个三角形的最大路径和。 参考程序I展示了一个简单的C语言实现，其中MaxSum函数使用递归方式实现了动态规划的思路。在main函数中，首先读入数字三角形的数据，然后调用MaxSum(1,1)获取结果并输出。 这两个问题都展示了动态规划在解决优化问题上的强大能力，尤其是在处理有重叠子问题和最优子结构的问题时。通过对子问题的分解和组合，动态规划能有效地找出全局最优解，避免了穷举所有可能性的高时间复杂度。