在很多年以前，写过一篇再聊动态规划，时至今日，有了更多的一些想法。

总结：

（1）写出状态转移方程（看问题的角度，状态和状态转移）

（2）自顶向下（递归搜索）和自底向上（动规实现）

（3）空间换时间，记忆化（缓存），变量优化（整体上动态规划并不是高效的算法，但是是一种优秀的算法思想）

（4）动态规划的题目几乎是最多的，同时在思路上也是非常优美的

（5）做题的选择：递归搜索，记忆化去冗余和动态规划（依据个人品味来定）

最长上升子序列 ：维护一个一维状态列表

最长递增子序列：维护两个一维状态列表

最长公共子序列：维护一个二维状态列表

最长连续序列：Hard类型，不用DP也可以做

最大连续子序列乘积，和求和相比，是更加松弛的DP，需要同时考虑当前值和历史值的乘积。

1.最长重复子数组

题目描述：给两个整数数组A和B，返回两个数组中公共的，长度最长的子数组的长度。举例如下：

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。

2.单词拆分

3.摆动序列

4.不同路径

这是一道经典的动态规划的题目。该题中，网格中是没有障碍物的，如果，网格中有障碍物呢？不同路径II，从这道题目延伸开来，可以思考几个有趣的问题：

（1）如何记录所有的移动路径？

（2）找到最短路径？

也就是说，基于动态规划的解法存在最优值和最优解的问题。最优值是一个值，也就是一个确定的数。最优解是决策组合，是一个过程，是解决问题的步骤。有些情况下，不一定需要满足最优条件。举例如下：

（1）找值。不同的二叉搜索树

（2）找解。不同的二叉搜索树II

5.三角形最小路径和

题目描述：给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。举例如下：

例如，给定三角形：
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

一种解法如下：

def minimumTotal(triangle):
        if len(triangle) == 0:return 0
        row = len(triangle) - 2
        for row in range(row, -1, -1):
            for col in range(len(triangle[row])):
                triangle[row][col] += min(triangle[row+1][col],triangle[row+1][col+1])
        return triangle[0][0]

6.经典题目：最短路径和，编辑距离，最大子数组的和，买卖股票的最佳时间。

实际上，买卖股票的最佳时间这个问题，可以转化为计算股票收益Diff的最大子数组的和。