62. Unique Paths

https://leetcode.com/problems/unique-paths/

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

img

非常基础的动态规划问题。用dp[i][j]表示到达grid[i][j]的路径数，那么

dp[i][j] = dp[i-1][j] + dp[i][j-1]

def uniquePaths(self, m: int, n: int) -> int:
	dp = [[0 for _ in range(n)] for _ in range(m)]
	for i in range(m):
	    for j in range(n):
	        if i == 0 and j == 0:
	            dp[i][j] = 1
	        else:
	            if i > 0:
	                dp[i][j] += dp[i-1][j]
	            if j > 0:
	                dp[i][j] += dp[i][j-1]
	return dp[-1][-1]

因为这个动态规划的累加是有序的，所以至多用一个一维数组就够了，用来记录dp[i-1][j]：

def uniquePaths(self, m: int, n: int) -> int:
	dp = [0 for _ in range(n)]
	for i in range(m):
	    for j in range(n):
	        if i == 0 and j == 0:
	            dp[j] = 1
	        else:
	            if i > 0:
	                # dp[i][j] += dp[i-1][j]. do nothing
	                pass
	            if j > 0:
	                dp[j] += dp[j-1]
	return dp[-1]

时间复杂度为$O(mn)$。

72. Edit Distance

https://leetcode.com/problems/edit-distance/

这个动态规划的递推式要想出来还是比较简单的。首先，令dp[i][j]为将word1[:i]和word2[:j]变成同样字符串所需的最小步数。根据和维特比算法类似的思路，可以看出：

  • 如果word1[i-1]和word2[j-1]相同，那么dp[i][j]=dp[i-1][j-1]（否则，dp[i-1][j-1]不是word1[:i-1]和word2[:j-1]之间的最短距离。这是维特比算法的思路。之后不再解释）
  • 或者可以给word1[:i-1]后面加个word2[j-1]，则dp[i][j] = dp[i][j-1] + 1；或者给把word1[i-1]删掉（跟给word2后面加个word1[i-1]是一样效果），则dp[i][j] = dp[i-1][j] + 1；或者把word1[i-1]替换成word2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1。

综上，时间复杂度为$O(mn)$，$m, n$为两个字符串的长度。

def minDistance(self, word1: str, word2: str) -> int:
	# dynamic programming
	# dis[i][j] = min distance between word1[:i] and word2[:j]
	# focus on (i-1)th word of word1 and (j-1)th word2(denoted by c and d)
	# 1. if replace c -> d: dis[i][j] == dis[i-1][j-1] + 1
	# 2. add a d to word1: dis[i][j] == dis[i][j-1] + 1
	# 3. delete c: dis[i][j] == dis[i-1][j] + 1
	# 4. c == d: dis[i][j] == dis[i-1][j-1]
	
	dp = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
	# initialize
	for i in range(len(word1)+1):
	    dp[i][0] = i
	for j in range(len(word2)+1):
	    dp[0][j] = j
	
	for i in range(1, len(word1)+1):
	    for j in range(1, len(word2)+1):
	        if word1[i-1] == word2[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[-1][-1]