北京大学动态规划课件：优化求解与数字三角形最大和

动态规划课件（北京大学）主要涵盖了动态规划的基本概念、算法应用以及解决实际问题的方法。课程的核心内容围绕着两个实例展开： 1. Fibonacci数列的求解：通过递归函数`f(int n)`展示如何计算斐波那契数列的第n项，但指出树形递归存在冗余计算。课程讲解了如何通过动态规划思想避免重复计算，引入了一个数组`f[n+1]`，初始化前两项，然后用循环计算剩余项，这种方法减少了计算量，提高了效率。 2. 数字三角形的最大路径和问题：该部分涉及一个二维数组表示的数字三角形，要求找到从顶部到底边的路径，使得路径上所有数字之和最大，且只给出最大和，不需具体路径。动态规划在此问题中的应用表现为定义状态`D(r,j)`表示第r行第j个数字，`MaxSum(r,j)`表示对应路径的和。递推公式表明，当到达最后一行时，最大和即为该位置的数字；否则，取左下和右下两个相邻位置的最大和加上当前位置的数字。课程提供了一个C++程序，使用递归函数`longestPath(int i, int j)`来实现此算法。 整个课程强调了动态规划在解决这类优化问题时的优势，通过分治策略和自底向上的方法，避免了重复计算，显著提升了算法的效率。参与者不仅能掌握动态规划的基本原理，还能通过实践案例深化理解和应用能力。