动态规划解题思路：

    1. 定义 **dp** 数组
    2. 得到状态转移方程
    3. 初始化 dp 数组

    优化：滚动数组

    • 有些时候，第 i 个时刻的状态只和第 i-1、第 i-2 等有限个状态有关，可以用有限个变量代替 dp 数组，降低空间复杂度

    题目汇总：

    leetcode 动态规划汇总

    [容易] 70. 爬楼梯
    [中等] 62. 不同路径
    [中等] 64. 最小路径和
    [中等] 198. 打家劫舍
    [容易] 53. 最大子序和
    [中等] 322. 零钱兑换
    [困难] 42. 接雨水
    [困难] 85. 最大矩形
    [中等] 221. 最大正方形
    [容易] 121. 买卖股票的最佳时机
    [容易] 122. 买卖股票的最佳时机 II
    [中等] 714. 买卖股票的最佳时机含手续费
    [中等] 139. 单词拆分
    [中等] 152. 乘积最大子数组
    [中等] 300. 最长递增子序列
    [困难] 32. 最长有效括号
    [中等] 96. 不同的二叉搜索树
    [容易] 剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫环）
    对于字符串，一般使用二维 dp 数组：
    [困难] 10. 正则表达式匹配
    [中等] 5. 最长回文子串
    [困难] 72. 编辑距离
    [中等] 1143. 最长公共子序列
    [中等] 718. 最长重复子数组