动态规划：费氏数列引例与优缺点分析

Chapter 4 of the textbook discusses Dynamic Programming, focusing on finding all possible multiplication combinations and calculating the number of multiplications needed for each combination. The algorithm presented in this chapter fills in each item on diagonal d of a matrix for a given range of values. This technique is illustrated with an example involving the Fibonacci sequence. The Fibonacci sequence, discovered by Italian mathematician Leonado Fibonacci in the 13th century, starts with 0, 1 and each subsequent number in the sequence is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on. This sequence exhibits some interesting properties, such as the sum of the first two numbers equaling the third number, and the ratio of consecutive numbers approaching the golden ratio of 0.618. A recursive algorithm for calculating Fibonacci numbers is presented, which is simple and easy to write and debug, but has low efficiency due to a large amount of repetitive calculations. This inefficiency can be analyzed using both intuition and time complexity analysis. While the algorithm is easy to understand, it suffers from redundant computations which make it less efficient in terms of runtime. In conclusion, Chapter 4 provides insights into Dynamic Programming by exploring multiplication combinations and their associated costs, along with a practical example of the Fibonacci sequence to illustrate the concepts discussed. The use of dynamic programming can lead to more efficient algorithms compared to recursive approaches, demonstrating the trade-offs between simplicity and performance in algorithm design.