动态规划

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

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

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

本章节分为 3 个部分:

  • Part 1

    • 最大子序和

    • 爬楼梯

    • 买卖股票的最佳时机

  • Part 2

    • 打家劫舍

    • 零钱兑换

    • 跳跃游戏

  • Part 3

    • 不同路径

    • Longest Increasing Subsequence

    • 单词拆分

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