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) |