动态规划法在程序设计中的应用

Dynamic Programming in Application of Computer Programming

探讨动态规划法的本质及在计算机程序设计中的应用。提出求解Fibonacci序列的3种算法,即递归法、自底向上和自顶向下动态规划法,证明将动态规划法用于程序设计,能降低算法的时间复杂度和空间复杂度。

The nature of dynamic programming and its application for computer programming are discussed. We present three methods for solving Fibonacci sequence, which are the recursive method, bottom-up approach and top-down approach respectively. The analysis about time complexity and space complexity for three algorithms is demonstrated that if use dynamic programming in computer programming, the time and space complexity will be decreased.