递归方法求解的基本思路-程序设计基础12_2_动态规划
在程序设计中,递归方法是一种常用的求解方法,但递归方法也存在一些问题,如重叠子问题等。为了解决这些问题,需要使用动态规划来优化递归方法。
**递归方法的基本思路**
递归方法的基本思路是将问题分解成更小的子问题,然后递归地解决这些子问题,最后将子问题的解组合起来得到原始问题的解。在递归方法中,每个子问题的解都需要计算多次,这将导致计算时间的增加。
**动态规划**
动态规划是一种优化递归方法的方法,它可以避免递归方法中的重叠子问题。动态规划的基本思路是将问题分解成更小的子问题,然后将每个子问题的解保存起来,最后将子问题的解组合起来得到原始问题的解。
**例子:数字三角形**
例如,数字三角形问题可以使用递归方法来解决。假设我们需要计算数字三角形的最大路径和,可以定义一个函数MaxSum(i, j)表示从第i行的第j个数字到底边的最佳路径上的数字之和。那么,我们可以使用递归方法来计算MaxSum(i, j),即:
* 如果走D(i+1, j),那么得到的MaxSum(i, j)就是MaxSum(i+1, j) + D(i, j);
* 如果走D(i+1, j+1),那么得到的MaxSum(i, j)就是MaxSum(i+1, j+1) + D(i, j)。
选择往哪里走,就看MaxSum(i+1, j)与MaxSum(i+1, j+1)哪一个更大。
**贪心法**
贪心法是动态规划的一种特殊情况,它是指在求解过程中,每一步都采用一种局部最优策略,逐渐缩小问题范围和规模,最后把每一步结果合并起来得到一个全局的最优解。贪心法的特点是,在求解过程中,每一步都可以选择当前的局部最优解,以便逐渐接近最优解。
**动态规划的特点**
动态规划的特点是:
* 空间换时间:动态规划可以将计算时间换成空间,以避免重复计算。
* 不重复求解:动态规划可以避免递归方法中的重叠子问题。
**递归的重叠子问题**
递归的重叠子问题是指在递归调用中,计算某个值需要去计算相同的子问题,导致对同一个值计算了多次。为了避免这种情况,可以使用动态规划来保存每个子问题的解,以便下次使用时可以直接调用保存的值,而不是再计算一次。
递归方法是程序设计中的一种常用方法,但它也存在一些问题,如重叠子问题等。为了解决这些问题,需要使用动态规划来优化递归方法。动态规划可以避免递归方法中的重叠子问题,并且可以将计算时间换成空间,以提高计算效率。