Jimmy Shen bio photo

Jimmy Shen

Machine Learning Engineer and Software Engineer

Email Github

Summary of Dynamic Problems

Summary of Dynamic Problems

Problem State Transitions Time Space
LIS (i) all j<i O(n^2) O(n)
LCS (i, j) dp[i-1][j-1]+1 if text1[i]==text2[j]
max(dp[i-1][j], dp[i][j-1]), otherwise.
O(NM) O(NM)
TSP (pos, mask) all n cities O(2^nn^2) O(n2^n)