64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
思路分析：
详细的分析过程参见： https://leetcode.com/problems/minimum-path-sum/discuss/23457/C%2B%2B-DP
方法是动态规划，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] ，但是这里要特别注意的是对边界条件的处理（即对 dp[0][0] 的处理、对 dp[0][j] 的处理以及对 dp[i][0] 的处理）。
代码如下：
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return None
dp = [grid[0][0]] * len(grid)
for i in range(1, len(grid)):
dp[i] = dp[i-1] + grid[i][0]
for j in range(1, len(grid[0])):
dp[0] += grid[0][j]
for i in range(1, len(grid)):
dp[i] = min(dp[i-1], dp[i]) + grid[i][j]
return dp[-1]
代码说明如下：
- 第 9 行体现的是对
dp[0][0]这个边界条件的处理； - 第 10 ~ 11 行体现的是对
dp矩阵第 1 列的处理，这里是固定j=0，让i从 1 增加到len(grid)； - 然后第 12 ~ 15 行是从第 1 列开始逐列地向右推进，直至到达
grid的最后一列。在这期间，第 13 行首先进行dp[0] += grid[0][j]是要先计算出dp最上面的一个元素，这实际上是对dp[0][j]这个边界条件的处理。第 15 行便是动态规划的核心。 - 时间复杂度：
（
、
分别是
grid的行数和列数），空间复杂度：。
70. Climbing Stairs
题目描述：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 stepsExample 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
思路分析：
参见： https://leetcode.com/problems/climbing-stairs/discuss/25299/Basically-it's-a-fibonacci.
本题的实质是一个斐波那契数列问题，解决方法是动态规划，核心是 dp[n] = dp[n-1] + dp[n-2] 。参照《剑指offer》上的斐波那契数列问题，可以写出如下代码：
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
pre, cur = 1, 2
for i in range(n-1):
pre, cur = cur, pre + cur
return pre
72. Edit Distance
题目描述：
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
思路分析：
参见： https://leetcode.com/problems/edit-distance/discuss/25846/C%2B%2B-O(n)-space-DP
基于上述链接中作者的分析，个人觉得在这个问题中，各状态之间的转移轨迹和机器人在二维方格中的运动过程有点类似（只不过这一次除了可以向右走和向下走之外，还可以沿斜向右下 45 ° 角的方向走）。状态转移方程如下：
如果这个问题换一个角度来思考：假设初始时给定的两个单词分别为 word1 和 word2 ，由于总共允许的操作方法只有三种：插入、删除、替换，将它们分别记为 、
、
（其中
），则从
word1 到 word2 必是由以上三种操作经过若干种排列组合而得到的。记总的操作数为 ，则有
其中， ，
，
。
现在我们要求的是 ，如果一下子要求出
的值肯定不好求。那怎么办呢？我们可以将这个大问题分解一下，假设如下是针对某一个具体问题的
dp 矩阵：
[[ 0 1 2 3 4 5 6 7 8 9]
[ 1 1 2 3 4 5 6 7 8 9]
[ 2 1 2 2 3 4 5 6 7 8]
[ 3 2 1 2 3 4 5 6 7 8]
[ 4 3 2 1 2 3 4 5 6 7]
[ 5 4 3 2 1 2 3 4 5 6]
[ 6 5 4 3 2 1 2 3 4 5]
[ 7 6 5 4 3 2 1 2 3 4]
[ 8 7 6 5 4 3 2 1 2 3]
[ 9 8 7 6 5 4 3 2 1 2]
[10 9 8 7 6 5 4 3 2 1]]
这个矩阵向下是 i 轴，向右是 j 轴。考察矩阵中的任意一个元素 dp[i][j] ，它是怎么得来的呢？首先一种最省操作数的方式是什么也不做，即 dp[i][j] = dp[i-1][j-1] ；另外一种是必须要做一步，这个时候 dp[i][j] 可以由它正上方、正左方或左上角的元素加 1 得到，具体是哪个元素加 1 要看哪个元素的值最小。这样，我们从两个单词都为空的状态开始，逐个地添加字母到 word1 和 word2 中，每添加一个字母，我们都计算一次最小操作数。当两个单词都添加完所有的字母后，一定能在上述的 dp 矩阵中找到一条路径，使得不仅最终总的操作数是最少的，甚至每新增一个字母时，这条路径的操作数始终都是最少的（如上述矩阵中恒为 1 的那条主对角线路径）。
上述的思路本质上还是穷举，只不过每添加一个字母都会进行一次动态规划，而且会将历史最优路径记录下来，避免重复地对已经规划过的路径重新进行规划，因此时间复杂度必为 （
分别是两单词的长度）。可以优化的地方是空间上的消耗，只需要上述矩阵中的一列就可以了，没必要保存整个
dp 矩阵。
空间优化前的代码：
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if not word1 or not word2: # 这里是为了避免后面出现索引越界的情况
return len(word1) or len(word2)
l1, l2 = len(word1), len(word2)
dp = [[0] * (l2+1) for _ in range(l1+1)] # 注意dp矩阵是多一行和一列
for i in range(1, l1+1): # i要往后多遍历一位，下同
dp[i][0] = i
for j in range(1, l2+1): # j也要往后多遍历一位，下同
dp[0][j] = j
for i in range(1, l1+1):
for j in range(1, l2+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
return dp[l1][l2]
空间优化后的代码：
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if not word1 or not word2:
return len(word1) or len(word2)
l1, l2 = len(word1), len(word2)
dp = [0] * (l2+1)
for j in range(1, l2+1): # 初始化第一行
dp[j] = j
for i in range(1, l1+1): # 索引必须要到l1+1
upleft = dp[0] # 由于要用到左上角的值，所以要单独记下来
dp[0] = i # 初始化第一列
for j in range(1, l2+1): # 索引必须要到l2+1
upleft_dynamic = dp[j] # 左上角的值必须要动态更新
if word1[i-1] == word2[j-1]: # 这里是word1[i-1]和word2[j-1]比，而不是word1[i]和word2[j]比
dp[j] = upleft
else:
dp[j] = min(upleft, dp[j], dp[j-1]) + 1
upleft = upleft_dynamic
return dp[l2] # 或者 return dp[-1]
75. Sort Colors
题目描述：
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]Follow up:
- A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.- Could you come up with a one-pass algorithm using only constant space?
代码：
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums)-1
for i in range(len(nums)):
while nums[i] == 2 and i < right:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
while nums[i] == 0 and i > left:
nums[i], nums[left] = nums[left], nums[i]
left += 1
if i == right:
break
return nums
说明：上述代码中，left 是 0 的右边界，right 是 2 的左边界，如下：
left right
| |
[0 0 | 1 1 | 2 2]
| |
