使用递归去解决问题虽然代码简洁、简单,但是效率不高。很多用递归解决的算法题,如果用动态规范来解决,效率会更高。
动态规划(dynamic programming )是通过组合子问题的解决,从而解决整个问题的算法。英文中的 programming
,指的是一种规划,而不是计算机代码。
动态规划适用于子问题不是独立的情况,对每个子问题只求解一次,使用数组来建立一张表格,来存放被分解成众多子问题的解,从而避免重复计算相同的子问题。
本章节分为 3 个部分:
Part 1
最大子序和
爬楼梯
买卖股票的最佳时机
Part 2
打家劫舍
零钱兑换
跳跃游戏
Part 3
不同路径
Longest Increasing Subsequence
单词拆分
阅读完本章节,你将对动态规划算法有更加熟悉对了解。