11.Dynamic Programming.md

第八课：动态规划 Dynamic Programming

DP四要素：
1.定义状态： dp[i][j]的意义 最后一步 化成子问题
2.返回什么东西
3.初始化 初始化一个二维的动态规划时 就去初始化第0行和第0列 和 边界情况
4.递推公式：怎么从初始化里面推测想返回的值

总体来说DP的两种写法：

1. 记忆化搜索方式：自上而下：DFS+Memoriztion (todo 等DFS刷完了就知道了)
   
2. 多重循环：traditional 写法：定义数组记录状态 两种实现没有区别，思维模式一个正向，一个逆向
   自下而上 自上而下
   

什么情况下使用动态规划?
满足下面三个条件之一，则 极有可能 是使用动态规划求解:
• 统计方案个数 ：1.有多少中方式走到右下角 2.有多少中方法选出K个数使得和是sum 运算：+
• 求最大值最小值：1.从左上角走到右下角路径的最大数字和 2.最长上升子序列长度 运算：min max
• 判断是否可行 1.取石子游戏，先手是否必胜 2.能不能选出k个数使得和是Sum 运算：and or

什么时候不用动态规划？
• 所有方案而不是方案数 （递归+深度搜索）
• 集合而非序列
• 暴力算法已经是多项式级别复杂度
动态规划擅长优化指数级别(2^n)到多项式级别(n^2)

动态规划 vs 递归???
递归：从上到下，然后会很多重复计算，时间复杂度为指数型
动态规划：从下到上，用数组记录下来值，简化时间复杂度。
记忆化搜索：带存储的递归，减少重复计算。

动态规划 vs 贪心算法？？？
贪心算法是每一步都用最优解法，例如，硬币问题，第一步就用最大硬币，第一步就可能走遍。
动态规划是选取最优解

递归: BDF:使用queue实现 DFS: 递归 or stack 求从一个点访问到的所有点...不用回退. 如果要求输出所有最短路径则需要DFS+BFS. Backtrack: combination 一个点可以要可以不要，所以是2的n次方.打印/输出所有路径的问题一定是回溯.打印或输出所有组合/排列的问题：combination/permutation （eg: subsets/permutations 问题） DP: 从小到大思考:普通递归，从大到小思考：记忆化搜索（带存储的dfs）。

1.坐标型DP

i个数：a[0], a[1], ..., a[i-1] 给定输入为序列或者网格/矩阵 动态规划状态下标为序列下标i或者网格坐标（i，j） f[i]以a[i]结尾的某种性质 求f[n] f[i][j] 到坐标（i，j）的路径的性质 求f[m-1][n-1]
初始化设置f[0]的值、f[0][0...n-1]的值 二维空间优化：如果f[i][j]的值值依赖于当前行和前一行，则可以用滚动数组节省空间

最简单的动态规划类型，给定一个序列或网格

• 0062.Unique Paths (!!M)
  Solution: 状态: f[i][j]=有多少种方式从左上角走到(i, j); 转移方程：f[i][j] = f[i][j-1]+f[i-1][j].
• 0063.Unique Paths II (M)
  Solution: 转移方程：f[i][j] = 0 if it is obstacle else f[i][j-1]+f[i-1][j]).
• 0064.Minimum Path Sum (M)
  方法一：dp, 方法二：空间优化 延伸题目：求路径 Solution: dp[i][j]=the minimum path sum to (i, j); dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]). DP works because we can pre compute two directions ... but we cannot pre-compute 4 directions or more .. in those cases Djikstra would be better.
• 0361.Bomb_Enemy.py (M) Solution: brutal force: 上下左右四个方向去找能炸死多少人即可。 DP解法: 把(i, j)位置能炸死多少敌人提前计算好放入二维数组中， up[i][j]=在(i,j)位置能向上炸的敌人数目.
• 0120.Triangle (M)
  
  • DFS: Traverse • DFS: Divide Conquer • Divide Conquer + Memorization • Traditional Dynamic Programming. Solution: dp[i][j] = min(triangle[i][j] + dp[i-1][j], triangle[i][j] + dp[i-1][j-1]), rolling array to reduce space to O(N).
• 0070.Climbing Stairs (E)
  Solution:1.状态定义dp[i] 从下至上到达第i个台阶的时候有的不同的方法. 2.求dp[n]. 3.初始化 dp[1] = 1 dp[2] = 2. 4.递推公式 dp[n] = dp[n-1] + dp[n-2]. time complexity O(n)
• 0746.Min Cost Climbing Stairs (E)
  跳跃游戏 I && II 这个题最优的方法是使用“贪心法”，动态规划复杂度较高
• 0055.Jump Game.java TODO:贪心算法
  
  solution 1: dp - TLE. solution 2: greedy - O(N)
• 0045.Jump_Game II
  Greedy算法：第一步可以跳到比如位置10，也就是说0-10我们都可以一步跳到，那我们就在0-10这些位置中，选一个位置i跳第二步，看看第二步能跳到最远的地方是哪里，比如是最远的是从位置6跳到位置28，那么就说明两步可以跳到位置28，也就是说11-28我们可以通过两步跳到，那我们就继续在11-28这些位置中，选一个位置i跳第三步.........这个greedy的思想非常重要，要熟记！！

最长序列型DP

i个数：a[0], a[1], ..., a[i-1]...a[n-1] 其实是坐标型动态规划，并不是序列型动态规划 dp[i]都是定义以a[i]结尾的最长... dp = [n] 求dp[n]
Note: subarray/substring 必须连续，subsequence/subsets 不需要连续

• 0674.Longest Continuous Increasing Subsequence (E)
  Solution: dp[i] = 以i结尾(包括i)的最长连续子序列; dp[i] = dp[i-1] + 1 if nums[i]>nums[i-1]; solution 2: 同向双指针（滑动窗口）
• 0300.Longest Increasing Subsequence (!!!M)
  solution1: tradition dp O(N*N). solution2: 时间复杂度优化. Solution: 不需要连续，所以不是dp[i] = dp[i-1] + 1，而是所有的j之前的i都有可能, 所以转移方程是 dp[j] = max(dp[i] + 1 for i<j and nums[i]<nums[j]) dp + binary search (O(NlogN))的算法也很重要！dp[i] = the maintianed array with i as the possible increadsing numbers, dp should be an orderd array: if nums[i] > the last item in dp, then append nums[i] to dp, else then将sorted arr中最接近num的数用num取代, by using binary search. same as 35. Search Insert Position.
• 0673.Number_of_Longest_Increasing_Subsequence (!!M)
  Solution: dp=以i为结尾的最大的长度; cnt=以i为结尾的最大的长度的个数; 在nums[j]>nums[i]的情况下：cnt[j]+=cnt[i] if dp[j]=dp[i]+1.
• 0279.Perfect Squares (!!M)
  Solution: f[j]=the least number of perfect square numbers which sum to i; f[j] = min(f[j-i^2]+1) for i^2<=j; Time complexity: j is from 0 to n, i is from 0 to j^0.5, so O(N^1.5); solution 2: level order BFS. Given a N-ary tree, where each node represents a remainder of the number n subtracting a square number, our task is to find a node in the tree, which should meet the conditions or remainder=0. bfs的层数就代表了所需要perfect squares的个数. Time complexity: 比较复杂最后是 O(n^(h/2)), where h is the height of the N-ary tree, h is 0 to 4.
• 0354.Russian_Doll_Envelopes (H)
  solution 1 dp - O(N^2): Similiar with 300. LIS; sort the list first envelopes.sort(key = lambda x: (x[0], x[1])), here we not only compare nums[j]>nums[i], but instead both the width and height; TLE. Solution 2: sort the evelopes first (tricky in sorting order!!), then 用length来做300. LIS - O(nlogn)
• 0368.Largest_Divisible_Subset (M)
  Solution: 1.define state: dp[i] represent the largest number subset which end with nums[i]

TODO：403. Frog Jump (H)

2.位操作动态规划

&与 |或 ^异或 ！非 逐位操作

• 0338.Counting_Bits.py (E)
  Solution: 状态dp[i]=i的二进制中有多少个1; dp[i] = dp[i >> 1] + i % 2

3.序列型DP!!

序列型特点：前i个，最小、方式数、可行性

序列型和坐标型区别：
1.给定一个序列
动态规划方程f[i]中的下标i表示前i个元素a[0], a[1], ..., a[i-1]的某种性质
坐标型的f[i]表示以a[i]为结尾的某种性质
2.初始化中，f[0]表示空序列的性质
– 坐标型动态规划的初始条件f[0]就是指以a[0]为结尾的子序列的性质

序列+状态型动态规划：当思考动态规划最后一步时，这一步的选择依赖于前一步的某种状态

• 0256.Paint_House.py (M)
  Solution: dp[i][j] means the minimum cost to paint house i to be color j; dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]).
• 0265.Paint_House_II.py (H)
  首先可以按照常规的dp方法去解题，发现时间复杂度比较高 kkn，思考优化方法。提前计算优化复杂度为 k*n!!!
  Solution: dp[i][j]=minimum cost to paint the ith house the be color j; dp[i][j] = dp(min in the (i-1)th row) + costs[i][j]. In order to find dp(min in the (i-1)th row), we can find the position for the 1st and 2nd min in the i-1 th row first, then in the ith row calcuation, if j==1st_min_pos, then dp[i][j]=2nd_min + costs[i][j], else dp[i][j]=1st_min + costs[i][j]
• 0198.House_Robber.py (E)
  Solution: f[i]=the max profit when reaching ith house; f[i] = max(rob ith = f[i-2]+nums[i], not rob ith = f[i-1]) 空间优化：dp[i] 之和 dp[i-2]与dp[i-1]有关，所以可以用prevMax和currMax来代表dp[i-2]与dp[i-1].
• 0213.House_Robber_II.py (!!M)
  Solution: 房子形成了一个环，所以第一个房子和第N个房子不能同时偷，我们可以把问题分成两个问题来解决：1. 房子1没偷：问题变成了对房子2:N做House robber I的问题; 2. 房子N没偷：问题变成了对房子1:N-1做House robber I的问题.
• 0152.Maximum_Product_Subarray.py (!!M)
  Solution: 最大值问题。maxDP[i]表示以i为结尾的subarray的最大的正数，minDP[i]表示以i为结尾的subarray的最小负数. 根据nums[i]的正负, 更新maxDP[i]和minDP[i].
• 0978.Longest_Turbulent_Subarray.py (!!M)
  Solution: dp: keep track of the lens of current increasing subarray and lens of current decreasing subarray. inc = dec + 1 if A[i]>A[i-1]; dec = inc + 1 if A[i]<A[i-1].

Buy and sell stock DP问题

• 0121.Best_Time_to_Buy_and_Sell_Stock (E)
  Solution: Only one transaction is allowed. Maintain a curr_min and a max_prof; max_prof = max(max_prof, price - curr_min)
• 0122.Best_Time_to_Buy_and_Sell_Stock_II (M)
  Solution: As many transaction as possible. make a transaction every time price[i]>price[i-1]
• 0309.Best_Time_to_Buy_and_Sell_Stock_with_Cooldown (M)
  Solution: Has to rest for one day before buy another stock. 分两个状态: hold and unhold: hold[i]=第i天有股票在手状态下的最大收益； unhold[i]=第i天没有股票在手状态下的最大收益, return unhold[-1]. hold[i] = max(hold[i-1], unhold[i-2]-prices[i]); unhold[i] = max(unhold[i-1], hold[i-1] + prices[i]) 学会画state machine.
• 0714.Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee (M)
  Solution: There is transaction fee when you sell. 分两个状态: hold and unhold: hold[i]=第i天有股票在手状态下的最大收益； unhold[i]=第i天没有股票在手状态下的最大收益 hold[i] = max(hold[i-1], unhold[i-1]-prices[i]); unhold[i] = max(unhold[i-1], hold[i-1] + prices[i] - fee)

TODO: 123 （H）
188（H）

4.划分型DP

特点：给定长度为N的序列或字符串，要求划分成若干段. 1.段数不限，或指定K段 2.每一段满足一定的性质
做法：
1.类似于序列型动态规划，但是通常要加上段数信息
2.一般用f[i][j]记录前i个元素（元素0~i-1）分成j段的性质，如最小代价

• 0091.Decode_Ways.py (M)
  Solution: f[i]=number of decode ways until i (not including i); f[i]=f[i-1]+f[i-2] if int(s[i-2:i])<=26 else f[i-1].解密数字串即划分成若干段数字，每段数字对应一个字母（partition，把一个完整的东西分成几段）
• 0139.Word_Break (!!M)
  Solution: solution 1: dp[i]=can partition until ith char?, not including i; dp[j]=true if (for i < j, there is dp[i]=True and s[i:j]is in wordDict). solution 2: bfs, solution 3: dfs + memorization (top-down dp)
• 0279.Perfect_Squares.py (!!M)
  solution 2: level order BFS. Given a N-ary tree, where each node represents a remainder of the number n subtracting a square number, our task is to find a node in the tree, which should meet the conditions or remainder=0. bfs的层数就代表了所需要perfect squares的个数. Time complexity: 比较复杂最后是 O(n^(h/2)), where h is the height of the N-ary tree, h is 0 to 4.
  TODO：时间复杂度+solution2

5.博弈型DP

博弈动态规划通常从第一步分析，而不是最后一步
– 因为局面越来越简单，石子数越来越少

• 0394.Coins_in_a_Line (M Lintcode)
  Solution1 dp: f[i]=面对i个石子，先手是必胜吗; f[i]=True if f[i-1] or f[i-2] 有一个是False Solution 2: 至于prev, curr有关，所以可以空间优化成O(1)了; Solution 3 数学: 只要是3的倍数就一定输 return n % 3 != 0
• 0486.Predict_the_Winner (M)
  f[i][j]=当石子还剩i到j时，先手最多能赢多少; f[i][j] = max(取左边A[i]-f[i+1][j], 取右边A[j]-f[i][j-1]), 注意f[i][j]与f[i+1][j]相关，所以i要从后往前遍历.
• 0877.Stone_Game (M)
  dp. dp[i][j] = how many more scores can someone have when left stones are [i, j] inclussive. dp[i][i] = piles[i]. dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). return dp[0][n-1]
• 1406.Stone_Game_III (H)
  dp. similar with 394. Coins in a Line. dp[i] = the max one can win with [i:] stones left. dp[i] = max(stones[i] - dp[i+1], stones[i] + stones[i+1] - dp[i+2], stones[i] + stones[i+1], stones[i+2] - dp[i+3])

6.背包型DP!!

解题技巧画矩阵，填写矩阵，值作为DP的维度，可用滚动数组优化

1. 背包问题的特点：题目要求加起来满足什么条件往往是背包；
   
2. 背包问题总重量一定要入状态！
   
3. 如果list中的items不能重复利用，那么状态要定义为成二维：前i个item拼出m的个数/可能性/方法/性质;
   
4. buffer layer
   

• 你有一个背包，背包有最大承重c • 商店里有若干物品，都是免费拿
• 每个物品有重量和价值
• 目标:不撑爆背包的前提下
– 装下最多重量物品
– 装下最大总价值的物品
– 有多少种方式正好带走满满一书包物品

背包问题，重量一定要入状态。状态: f[X]=最少用多少枚硬币拼出X; 转移方程：f[X] = min(f[X-1]+1, f[X-2]+1, f[X-5]+1, f[X])

• 0092.Backpack (!!M Lintcode)
  要求不超过M时能拼出的最大重量, 记录前i个物品能拼出哪些重量.背包里的物品不能重复使用，所有状态定义为二维 f[i][m]=能否用前i个物品拼出重量m; f[i][m] = f[i-1][m] (不放入，表示前i-1个物品就可以拼出m) or f[i-1][m-A[i-1]] (放入，表示前i-1个物品可以拼出m-A[i-1]); # 注意点1：这里要定义lens+1，这样就可以做一个buffer layer出来了; # 注意点2；这里循环i在外面，m在里面，千万别搞反了！！# 注意点3：由于buffer layer的存在，这里用nums[i-1]与m相比较.
• 0125.Backpack_II (!!M Lintcode)
  这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][j]表示前i件物品拼出重量j可以获得的最大价值。 f[i][j]=max{f[i-1][j] (不放入),f[i-1][j-A[i-1]]+V[i-1] (放入)}; return f[lens][M].
• 0562.Backpack_IV.py (!!M Lintcode)
  Solution:每个物品只能取一个递推公式：dp[i][j] 个数 = dp[i - 1][j - A[i - 1]] + dp[i - 1][j].所以k = 0记录能取多少次，每次+1，直到超过总数，最后加起来。
• 0563.Backpack_V (!!M Lintcode)
  优化：滚动素组，m*n维数组，压缩成2维数组，再压缩成1维数组. 一个num不能取多次，所有状态定义为二维 ，f[i][m]=前i个物品能拼出重量m有多少种方式。f[i][m] = 不放入 f[i-1][m] + 放入 f[i-1][m-A[i-1]] if m > nums[i]
• 0322.Coin_Change (!!M)
  TODO : 0518. Coin Change 2 (M) TODO: 377. Combination Sum IV (M)

7.区间型DP!!

给定一些序列/字符串，进行一些操作，求满足区间[i, j]的一些性质的题目
自然而然将状态定义为f[i][j]表示面对子序列[i, j]时的最佳性质。
经常用来处理sub-sequence, sub-string, sub-array的问题，
注意sub-sequence不需要连续，sub-string, sub-array必须是连续的

适合用记忆化搜索来做，但是也可以转化成普通dp，一般是从大到小的求值。 特点：
求一段区间的解max/min/count
转移方程通过区间更新
从大到小的更新

• 0877.Stone_Game.py (!!M)
  Solution1: 传统dp，不好理解 1.define state: dp[i][j] represent when facing num[i...j] the number of winning 2.dp[0][n-1] 3.dp[i][j] = nums[i] when i = j 4.transit function dp[i][j] = max{nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]}. Solution2: 记忆化搜索也可以做.
• 0005.Longest_Palindromic_Substring (!!M)
  题目问substring, substring就需要是连续的，题目要求Return the longest substr: dp[i][j]=from i to j (including j), is it a palindr? if s[i]==s[j]: dp[i][j] = dp[i+1][j-1]; 注意初始化对角线和相邻的，因为计算dp[i][j]需要用到dp[i+1][j-1]，所以要先算i+1, 再算i，所以i 是倒序遍历 solution Solution 2: central spread. 从中间c往两边遍历i--, j++，遍历两次：一次是i=c, j=c开始遍历， 一次是i=c, j=c+1开始遍历.
• 0312.Burst_Balloons (H)
  solution 1: dp[i][j] = max coin we can get from i to j, not including i, not including j. dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]* nums[k]* nums[j] for k in range(i+1, j)). solution 2: backtrack without memorizaiton - O(2^N). solution 3: 带memo的recursion; left = self.memoSearch(nums, i, k, memo); right=self.memoSearch(nums, k, j, memo); maxCoins = max(maxCoins, left + right + nums[i] * nums[k] * nums[j]).
• 0375.Guess_Number_Higher_or_Lower_II (M)
  DP. dp[i][j] = 数字在[i, j]范围内所需要的最小payment. dp[i][j] = mid + max(dp[i][mid-1], dp[mid+1][j]) for mid in range(i, j)
• 0516.Longest_Palindromic_Subsequence (!!M)
  题目问subsequence, subsequence不需要连续，题目要求Return the longest length: dp[i][j]=longest palindr from i to j; dp[i][j]=dp[i+1][j-1]+2 if s[i]==s[j] else max(dp[i+1][j], dp[i][j-1]);注意初始化对角线，因为计算dp[i]需要用到dp[i+1]，所以要先算i+1, 再算i，所以i is from (j, 0).
• 0647.Palindromic_Substrings (!!M)
  dp[i][j] = is s[i to j including i and j] a palindrome? dp[i][j] = True if s[i]==s[j] and (dp[i+1][j-1] or lens <=2). if it is True, then number of palindromic substring += 1.
• 1312.Minimum_Insertion_Steps_to_Make_a_String_Palindrome.py (H)
  dp 1143.Longest Common- Subsequence. 题目其实是求 n - (the longest palindromic subsequence in s); 也就是 to find the longest common subsequence between s and s[::-1]. which is same as 1143.Longest Common- Subsequence.

TODO:471.

8.双序列型DP(匹配类DP)!!

解题技巧画矩阵，填写矩阵

• 0072.Edit_Distance.py (!!H)
  f[i][j]=A前i个字符[0..i)和B前j个字符[0..j)的最小编辑距离; f[i][j]=min{1. f[i-1][j]+1 (f[i-1][j]表示A[0..i-1)就可以拼成B[0..j)了，所以A[0..i)要拼成B[0..j)需要删掉A[0..i)的最后一个字母); 2. f[i][j-1]+1 (B[0..j)需要删掉最后一个字母，即A[0..i)的后面需要增加一个字母); 3. f[i-1][j-1]+1 (A[0..i)的后面需要replace一个字母); 4. f[i-1][j-1] (if A[i-1]=B[j-1] 就不需要任何操作直接就是了)}

• 1143.Longest_Common_Subsequence.py (!!M)
  f[i][j]为A前i个字符A[0..i)和B前j个字符[0..j)的最长公共子串的长度，注意不包括i和j，前面有一层buffer layer非常重要，就像sputtering那样重要！ f[i][j]=f[i-1][j-1] + 1 when A[i-1]=B[j-1], else f[i][j]=max(f[i-1][j], f[i][j-1])) # 注意有了buffer layer之后，dp中的i对应的是text中的i-1,所以判断条件是when A[i-1]=B[j-1]

• 0115.Distinct_Subsequences.py
  求多少种方案. Solution: 1.dp[i][j] = the number of discinct subeseq until ith char in s and jth char in t. 2.if s[i]!=t[j], dp[i][j] = dp[i - 1][j] eg: rab, ra. 3. else: rabb, rab, dp[i][j] = dp[i-1][j] + dp[i-1][j-1], 品，细品！

• 0097.Interleaving_String.py (!!M)
  Solution:求可行性。f[i][j]=s3的前[0..i+j)个字符能否由s1前i个字符[0..i)和s2前j个字符[0..j)交错形成; f[i][j]=True when (s3[i+j-1]=s1[i-1] 且 f[i-1][j]=True 即s3的前[0..i+j-1)个字符能否由s1前i-1个字符[0..i-1)和s2前j个字符[0..j)交错形成) or (s3[i+j-1]=s2[j-1] and f[i][j-1]=True)

• 0718.Maximum_Length_of_Repeated_Subarray.py (!!M)
  subarr/substring的问题都similar with 1143.Longest Common Subsequence. since subarray has to be continuous, we define dp as dp[i][j] = the max lens of repeated subarray ended with A[i] and B[j] dp[i][j] = if A[i-1]==B[j-1]: dp[i-1][j-1] + 1; else: 0 cuz has ot be continuous. solution 2: binary search - (m+n)mlogm.

• 0583.Delete_Operation_for_Two_Strings (M)
  f[i][j] = the min number of steps needed to make word1[:i] and word[:j] the same; f[i][j]=f[i-1][j-1] when A[i-1]=B[j-1], else f[i][j]=min(f[i-1][j], f[i][j-1])) + 1. TODO: 1092

9.滚动数组优化

延伸：滚动数组（经常用于坐标型DP）+打印路径（要记录用的路径）结合？？？TODO没懂 第三讲

滚动数组优化一维，这类题目特点： f[i] = max(f[i-1], f[i-2] + A[i]); 由 f[i-1],f[i-2] 来决定状态 可以转化为 f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2]) 由f[(i-1)%2]和 f[(i-2)%2] 来决定状态。观察我们需要保留的状态来确定模数

二维动态规划空间优化，这类题目特点： f[i][j] = 由f[i-1]行 来决定状态， 第i行跟 i-1行之前毫无关系， 所以状态转变为f[i%2][j] = 由f[(i-1)%2]行来决定状态 小技巧：网格类的题目 正方形用右下角作为定位角 长方形可以用左上角和右下角作为定位角。例如221. Maximal Square

• 0198.House_Robber.py (E)
  Solution: 序列型动态规划。f[i]=the max profit when reaching ith house; f[i] = max(rob ith = f[i-2]+nums[i], not rob ith = f[i-1]) 空间优化：dp[i] 之和 dp[i-2]与dp[i-1]有关，所以可以用prevMax和currMax来代表dp[i-2]与dp[i-1].
• 0213.House_Robber_II.py (!!M)
  Solution: 房子形成了一个环，所以第一个房子和第N个房子不能同时偷，我们可以把问题分成两个问题来解决：1. 房子1没偷：问题变成了对房子2:N做House robber I的问题; 2. 房子N没偷：问题变成了对房子1:N-1做House robber I的问题.
• 0070.Climbing Stairs (E)
  Solution:1.状态定义dp[i] 从下至上到达第i个台阶的时候有的不同的方法. 2.求dp[n]. 3.初始化 dp[1] = 1 dp[2] = 2. 4.递推公式 dp[n] = dp[n-1] + dp[n-2]. time complexity O(n)
• 0221.Maximal_Square (M)
  Solution:dp[i][j]=以(i, j)为右下角的最大正方形的边长; dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 if matrix[i][j]=1.滚动数组不好优化，所以不优化了。
• 0062.Unique_Paths.py (M)
  
• 0064.Minimum Path Sum (M)
  方法一：dp, 方法二：空间优化 延伸题目：求路径 Solution: dp[i][j]=the minimum path sum to (i, j); dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]). DP works because we can pre compute two directions ... but we cannot pre-compute 4 directions or more .. in those cases Djikstra would be better.
• 0072.Edit_Distance.py (H)
  f[i][j]=A前i个字符[0..i)和B前j个字符[0..j)的最小编辑距离; f[i][j]=min{1. f[i-1][j]+1 (f[i-1][j]表示A[0..i-1)就可以拼成B[0..j)了，所以A[0..i)要拼成B[0..j)需要删掉A[0..i)的最后一个字母); 2. f[i][j-1]+1 (B[0..j)需要删掉最后一个字母，即A[0..i)的后面需要增加一个字母); 3. f[i-1][j-1]+1 (A[0..i)的后面需要replace一个字母); 4. f[i-1][j-1] (if A[i-1]=B[j-1] 就不需要任何操作直接就是了)}

10.记忆搜索

本质上:动态规划, 动态规划就是解决了重复计算的搜索 • 动态规划的实现方式: 循环(从小到大递推) • 记忆化搜索(从大到小搜索): 画搜索树 • 万金油

什么时候用记忆化搜索? 1. 状态转移特别麻烦，不是顺序性。2. 初始化状态不是很容易找到。 状态转移特别麻烦，不是顺序性。 • Longest Increasing continuous Subsequence 2D • 遍历x,y 上下左右四个格子 dp[x][y] = dp[nx][ny] • Coins in a Line III • dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1]); 初始化状态不是很容易找到 • Stone Game • 初始化dp[i][i] = 0 • Longest Increasing continuous Subsequence 2D • 初始化极小值 从大到小

适用的DP:博弈类-区间类-双序列

什么时候用记忆化搜索? 1. 状态转移特别麻烦，不是顺序性。2. 初始化状态不是很容易找到。d额 什么时候用记忆化搜索? 1. 状态转移特别麻烦，不是顺序性。2. 初始化状态不是很容易找到。

匹配类 除了有些题目可以用贪心，其他题目都不能用贪心法做。