https://leetcode.com/problems/interleaving-string/
比较直观的dp了，可以当作一维DP的模板

二维DP数组

  1. class Solution:
  2.     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
  3.         if len(s1) + len(s2) != len(s3):
  4.             return False
  5.         dp = [[False for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]
  6.         dp[0][0] = True
  7.         for i in range(0, len(s1) + 1):
  8.             for j in range(0, len(s2) + 1):
  9.                 if i + j == 0:
  10.                     continue
  11.                 dp[i][j] = ((i > 0) and (s3[i + j - 1] == s1[i - 1]) and dp[i - 1][j]) or ((j > 0) and (s3[i + j - 1] == s2[j - 1]) and dp[i][j - 1])
  12.         return dp[len(s1)][len(s2)]

一维DP数组

  1. class Solution:
  2.     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
  3.         if len(s1) + len(s2) != len(s3):
  4.             return False
  5.         dp = [False for j in range(len(s2) + 1)]
  6.         dp[0] = True
  7.         for i in range(0, len(s1) + 1):
  8.             for j in range(0, len(s2) + 1):
  9.                 if i + j == 0:
  10.                     continue
  11.                 dp[j] = (i > 0 and s3[i + j - 1] == s1[i - 1] and dp[j]) or (j > 0 and s3[i + j - 1] == s2[j - 1] and dp[j - 1])
  12.         return dp[len(s2)]

其实这种二维数字中，只用到上一行的，都可以转化成一维，转化起来也丝毫不费事，对比下两个代码就知道了。

延伸：72. Edit Distance

https://leetcode.com/problems/edit-distance/
遇到依赖前后状态的情况怎么办呢？

  1. class Solution:
  2.     def minDistance(self, a: str, b: str) -> int:
  3.         dp = [[math.inf for j in range(len(b) + 1)] for i in range(len(a) + 1)]
  4.         for i in range(len(a) + 1):
  5.             dp[i][0] = i
  6.         for j in range(len(b) + 1):
  7.             dp[0][j] = j
  8.         for i in range(1, len(a) + 1):
  9.             for j in range(1, len(b) + 1):
  10.                 if a[i - 1] == b[j - 1]:
  11.                     dp[i][j] = dp[i - 1][j - 1]
  12.                 else:
  13.                     dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
  14.         return dp[len(a)][len(b)]

其中dp[i][j - 1], dp[i - 1][j - 1]新旧两个状态都用到了。
比较简单的方法是用两个数组存新旧两个状态，并不断更新。
一个trick的方式是，只用一个数字存旧状态，这样旧可以啦。

  1. class Solution:
  2.     def minDistance(self, a: str, b: str) -> int:
  3.         dp = [math.inf for j in range(len(b) + 1)]
  4.         for j in range(len(b) + 1):
  5.             dp[j] = j # dp[0][j]
  6.         for i in range(1, len(a) + 1):
  7.             pre = dp[0] # dp[i - 1][0]
  8.             dp[0] = i # dp[i][0]
  9.             for j in range(1, len(b) + 1):
  10.                 curr = dp[j] # dp[i - 1][j]
  11.                 if a[i - 1] == b[j - 1]:
  12.                     dp[j] = pre
  13.                 else:
  14.                     dp[j] = min(dp[j - 1], curr, pre) + 1
  15.                 pre = curr # dp[i - 1][j - 1]
  16.         return dp[len(b)]