講了動態(tài)規(guī)劃：
一道題如何判斷用動態(tài)規(guī)劃來解袖迎，并且如何解猫牡，一共有以下幾個要素：
動態(tài)規(guī)劃一般可以回答以下三個問題：
a) 最優(yōu)解/Maximum/Minimum
b) Yes/No
c) Count(*) 2. ?方程 Function
然后在構(gòu)造動態(tài)規(guī)劃的解答的時候，主要分為下面四個步驟
- 狀態(tài) State
靈感,創(chuàng)造?力,存儲?小規(guī)模問題的結(jié)果 - 狀態(tài)之間的聯(lián)系,怎么通過?小的狀態(tài),來求得?大的狀態(tài)
- 初始化 Intialization：最極限的?小狀態(tài)是什么, 起點
- 答案 Answer： 最?大的那個狀態(tài)是什么,終點
以上是基礎(chǔ)算法班的知識捆昏，這節(jié)課主要講的是記憶化滾動數(shù)組優(yōu)化和記憶化搜索赚楚。
滾動數(shù)組優(yōu)化主要是如果遞推公式里，i的值只和有限個前值相關(guān)屡立，就可以優(yōu)化直晨，比如i只和i-1，i-2相關(guān)膨俐，那么只要開一個長度為2的數(shù)組循環(huán)利用就可以了勇皇。
記憶化搜索的主要用處是1. 當(dāng)DP的i不是只和前面的值有關(guān)的情況，比如說有可能是矩陣類型的搜索需要搜索四個方向焚刺，2.game的問題敛摘，兩個玩家你拿一個我拿一個這種用記憶化搜索比較容易一些
題目：
1. Longest Increasing Continuous Subsequence: 因為是連續(xù)的，所以后一個值只和前一個值有關(guān)系乳愉，所以可以用滾動數(shù)組優(yōu)化
2. Maximum Subarray: 利用前綴和數(shù)組
3. Maximal Square: 利用以某一個坐標為右下角的點兄淫，看看能不能形成正方形，并且記錄其邊長
4. Longest Palindromic Substring: 這題我從來都沒用動態(tài)規(guī)劃來解決過蔓姚，直接loop
5. Coins in a Line: 記憶化搜索中的game問題捕虽，只考慮當(dāng)前自己能夠獲得的值
6. Coins in a Line II: 同上題
7. House Robber : 可以用滾動數(shù)組來優(yōu)化
8. Maximum Product Subarray: 除了記錄當(dāng)前最小值和當(dāng)前最大值，關(guān)鍵是要把自己這個點加進去考慮
9. Longest Increasing Subsequence：這題的i和前面0~i-1個值都相關(guān)坡脐，所以沒法用滾動數(shù)組來優(yōu)化了
10. Longest Increasing Continuous subsequence II: 這題叫做滑雪道問題泄私，就是從最高處一直朝下滑。一道很好的記憶化搜索+backtracking的問題∩味耍可以再做一遍
