9.3 - 高算5

讲了动态规划：
一道题如何判断用动态规划来解，并且如何解，一共有以下几个要素：
动态规划一般可以回答以下三个问题：
a) 最优解/Maximum/Minimum
b) Yes/No
c) Count(*) 2. ⽅方程 Function
然后在构造动态规划的解答的时候，主要分为下面四个步骤

1. 状态 State
   灵感,创造⼒力,存储⼩小规模问题的结果
2. 状态之间的联系,怎么通过⼩小的状态,来求得⼤大的状态
3. 初始化 Intialization：最极限的⼩小状态是什么, 起点
4. 答案 Answer： 最⼤大的那个状态是什么,终点

以上是基础算法班的知识，这节课主要讲的是记忆化滚动数组优化和记忆化搜索。

滚动数组优化主要是如果递推公式里，i的值只和有限个前值相关，就可以优化，比如i只和i-1，i-2相关，那么只要开一个长度为2的数组循环利用就可以了。

记忆化搜索的主要用处是1. 当DP的i不是只和前面的值有关的情况，比如说有可能是矩阵类型的搜索需要搜索四个方向，2.game的问题，两个玩家你拿一个我拿一个这种用记忆化搜索比较容易一些

题目：
1. Longest Increasing Continuous Subsequence: 因为是连续的，所以后一个值只和前一个值有关系，所以可以用滚动数组优化

2. Maximum Subarray: 利用前缀和数组

3. Maximal Square: 利用以某一个坐标为右下角的点，看看能不能形成正方形，并且记录其边长

4. Longest Palindromic Substring: 这题我从来都没用动态规划来解决过，直接loop

5. Coins in a Line: 记忆化搜索中的game问题，只考虑当前自己能够获得的值

6. Coins in a Line II: 同上题

7. House Robber : 可以用滚动数组来优化

8. Maximum Product Subarray: 除了记录当前最小值和当前最大值，关键是要把自己这个点加进去考虑

9. Longest Increasing Subsequence：这题的i和前面0~i-1个值都相关，所以没法用滚动数组来优化了

10. Longest Increasing Continuous subsequence II: 这题叫做滑雪道问题，就是从最高处一直朝下滑。一道很好的记忆化搜索+backtracking的问题。可以再做一遍