Longest Common SubSequence
迷宫路径问题
最 easy 的就是给迷宫, 能够走的路径的个数, 变种有: 加了阻碍的路径个数, 迷宫的具有最小和的路径.
其他一些较为经典的 DP:
Edit distance 问题
走台阶问题, decode ways https://leetcode.com/problems/decode-ways/ , unique binary search trees
Longest Common SubSequence
LCS 是一个经典的 DP 问题.
- def findLength(A, B):
- ret = 0
- D = [0] * (len(B) + 1)
- for j in range(len(B)-1, -1, -1):
- if A[i] == B[j]:
- D[j+1] = D[j] + 1
- ret = max(D[j+1], ret)
- else:
- D[j+1] = 0
- return ret
来源: http://www.bubuko.com/infodetail-3437733.html