动态规划

使用递归去解决问题虽然代码简洁、简单，但是效率不高。很多用递归解决的算法题，如果用动态规范来解决，效率会更高。

动态规划(dynamic programming )是通过组合子问题的解决，从而解决整个问题的算法。英文中的 programming，指的是一种规划，而不是计算机代码。

动态规划适用于子问题不是独立的情况，对每个子问题只求解一次，使用数组来建立一张表格，来存放被分解成众多子问题的解，从而避免重复计算相同的子问题。

本章节分为 3 个部分：

• Part 1

  • 最大子序和

  • 爬楼梯

  • 买卖股票的最佳时机

• Part 2

  • 打家劫舍

  • 零钱兑换

  • 跳跃游戏

• Part 3

  • 不同路径

  • Longest Increasing Subsequence

  • 单词拆分

阅读完本章节，你将对动态规划算法有更加熟悉对了解。