Linear DP over arrays or sequences: Kadane, House Robber, Stocks, LIS
dp[i] summarizes optimal value up to i using transitions from previous states.
Use when the subproblem depends on a fixed number of previous positions.
Rolling variables/arrays for linear transitions (Kadane, house robber, simple stocks/LIS) with careful base cases and overwrite order.
# Subsequence DP Template (Edit Distance)
def edit_distance(s, t):
n,m=len(s),len(t)
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): dp[i][0]=i
for j in range(m+1): dp[0][j]=j
for i in range(1,n+1):
for j in range(1,m+1):
if s[i-1]==t[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[n][m]Max subarray ending at i
def kadane(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestdp[i]=max(dp[i-1],dp[i-2]+val)
def house_robber(nums):
prev2 = 0; prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1State machine for buy/sell/cooldown
def max_profit_one_tx(prices):
minp = float('inf'); best = 0
for p in prices:
minp = min(minp, p); best = max(best, p - minp)
return bestn log n with tails or O(n^2) DP
from bisect import bisect_left
def lis_length(nums):
tails=[]
for x in nums:
i=bisect_left(tails, x)
if i==len(tails): tails.append(x)
else: tails[i]=x
return len(tails)Linear or n log n for LIS.
Rolling vars or arrays.