---
tags: 動態規劃 DP, 最大子陣列 Maximum Subarray
---
# 動態規劃 DP
## 概念
1. 定義狀態
2. 轉移式
3. 答案 & 邊界條件
## 最大子陣列 Maximum Subarray
$dp(i)=以i結尾的最大子陣列$
$dp(i)=max\{dp(i-1)+a_i,\ a_i\}$
$ans=max\{dp(i)\},\ i=1\sim n$
* 時間複雜度：$O(n)\times O(1)=O(n)$
* $1D/0D問題$
## 最長遞增子序列 LIS
$dp(i)=以i結尾的最長遞增子序列$
$dp(i)=1\ or\ max\{dp(j)+1\},\ 1\leq j<i,\ a_j<a_i$
$ans=max\{dp(i)\},\ 1\leq i < n$
* 時間複雜度：$O(n)*O(n)=O(n^2)$
* $1D/1D問題$
## 最長共同子序列 LCS
$dp(i,\ j)=LCS(a_{1\sim i},\ b_{1\sim j})$
$dp(i,\ j)=dp(i-1,\ j-1)+1,\ only\ if\ a_i=b_j$
$else\ dp(i,\ j)=max\{dp(i,\ j-1),\ dp(i-1,\ j)\}$
$令|a|=m,\ |b|=n$
$則ans=dp(m,\ n)$
* 時間複雜度：$O(n^2)\times O(1)$
* $2D/0D問題$