动态龟化连载

1. 两个字符串最长字串:
   $dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & s_1[i]==s_2[j] \\ 0 & s_1[i] !=s_2[j] \end{cases}$dp[i][j]={dp[i−1][j−1]+10​s1​[i]==s2​[j]s1​[i]!=s2​[j]​

2. 两个字符串的最长公共子序列(LCS)
   $dp[i][j]= \begin{cases} max(dp[i][j-1], \space dp[i-1][j]) & s_1[i] !=s_2[j] \\ dp[i-1][j-1]+1, \space & s_1[i] =s_2[j] \end{cases}$dp[i][j]={max(dp[i][j−1], dp[i−1][j])dp[i−1][j−1]+1, ​s1​[i]!=s2​[j]s1​[i]=s2​[j]​

3. 最长递增子序列
   目标：max(dp)
   初始化：dp[i]=1
   $dp[i]=max(dp[j]+1) \qquad 0 \leq j <i \space and \space arr[i]>arr[j]$dp[i]=max(dp[j]+1)0≤j<i and arr[i]>arr[j]

4. 连续子数组的最大和
   目标：max(dp)
   $dp[i]= max(dp[i-1]+nums[i], \quad nums[i])$dp[i]=max(dp[i−1]+nums[i],nums[i])

5. 合唱队出列n-k人，留下k人构成中间高，两边矮的山峰形队列，求最大k
   和最长递增子序列一样，从左到右边，从右到左，两个dp相加，返回max(dp1,dp2)-1（重复计算）

6. 打家劫舍，邻居不偷
   目标：dp[-1]
   初始化：
   dp[0]= nums[0]
   dp[1] = max(nums[0],nums[1])
   $dp[i] = max(dp[i-2]+nums[i], \quad dp[i-1])$dp[i]=max(dp[i−2]+nums[i],dp[i−1])

7. 最小花费爬楼梯
   你可以爬一层或者两层，代价是你所在层的花费cost[i]
   目标：min( dp[-1] , dp[-2] )
   初始化：
   dp[0], dp[1] = cost[0], cost[1]
   $dp[i] = min(dp[i-1]+cost[i], \quad dp[i-2]+cost[i])$dp[i]=min(dp[i−1]+cost[i],dp[i−2]+cost[i])

8. n个物品涂k色方法数目，最多连续两个颜色相同
   目标：dp[-1]
   初始化：
   dp[0]=k
   dp[1] = k*k

$dp[i] = (dp[i-2] + dp[i-1]) \times ( k - 1)$dp[i]=(dp[i−2]+dp[i−1])×(k−1)

9. 股票1，某天卖出，问利益最大

$dp[i] = max(dp[i-1] ,\quad price[i]-min(price[:i-1]))$dp[i]=max(dp[i−1],price[i]−min(price[:i−1]))

10. 用3种颜色粉刷n个房子，邻居不同色
    
    11.爱丽丝抽卡游戏
    
    dp[x]表示目前点数为x情况下，获胜的概率
    $dp[x] = \frac{1}{w} \times ( dp[x+1]+...+dp[x+w]) \quad when \space 0 \le x \le k-1$dp[x]=w1​×(dp[x+1]+...+dp[x+w])when 0≤x≤k−1
    因此$x \le k+w-1$x≤k+w−1, ==>抽完后，牌面最大为k+w-1，因此建立一个[0,k+w-1]的dp数组
    对于$x=k-1$x=k−1处，我们开始倒推至最终目的地dp[0]。对于$x>=k$x>=k情况下，概率（dp[x]）不是1就是0，比较x与N，$x \le N$x≤N时候就为1，else 0。

11. 01矩阵里最大的正方形
    初始化，dp=matrix
    dp[i][j] 表示以$(i,j)$(i,j)为右下角的矩阵的最大边长值。
    $if dp[i][j] \space and \space dp[i-1][j-1] \space and \space dp[i-1][j] \space and \space dp[i][j-1]: \\ \\ dp[i][j] += min(dp[i-1][j-1] \quad,dp[i-1][j],\quad dp[i][j-1])$ifdp[i][j] and dp[i−1][j−1] and dp[i−1][j] and dp[i][j−1]:dp[i][j]+=min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])

12. 旅行票价最小花费

关键：如果今天不出行，不买票，如果今天出行，买票并且考虑之后的出行日期。
思路：倒着求dp。dp[i]表示,第i天之后旅行的最小花费。
目标求:dp[0]
$dp[i] = \begin{cases} min(dp[i+ 1] + costs[0], dp[i + 7] + costs[1], dp[i + 30] + costs[2]) & i \in days \\ dp[i+1] & i \notin days \end{cases}$dp[i]={min(dp[i+1]+costs[0],dp[i+7]+costs[1],dp[i+30]+costs[2])dp[i+1]​i∈daysi∈/​days​