Dynamic Programming

Veröffentlicht am

Introduction

职业规划原因今年计划自学Go语言，前两个月也断断续续用Golang刷了100道左右的算法题。然而:(最近一个月工作比较忙就搁置了一段，今天看了下https://github.com/xiaozhazi/leetcode_go 距上次commit已经有近一个月的时间了 - _ -#。

所以今天开始强制自己记录下个人解题过程以及go语言踩雷， 也便于随时复盘【其实是为了自我监督防止懒癌：）

LeetCode真题系列

Minimum Path Sum(64)

64 Minumum Path Sum

Question

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.

Analysis

从（0，0）走到（m-1，n-1）每个阶段只能选择向右或向下两种决策，且每个阶段都会对应一个状态集合。我们把状态定义为dp[i][j]表示从起点走到（i，j）位置时的最短路径长度。 因此它是一个多阶段最优解问题符合动态规划模型。

dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
直接动手上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func minPathSum(grid [][]int) int {
  if grid == nil || len(grid) == 0 {
	return 0
  }
  m, n := len(grid), len(grid[0])
  dp := make([][]int, m)
	
  for i := 0; i < m; i++ {
	dp[i] = make([]int, n)
  }
	
  dp[0][0] = grid[0][0]
  for i := 1; i < m; i++ {
	dp[i][0] = dp[i-1][0] + grid[i][0]
  }
  for i := 1; i < n; i++ {
	dp[0][i] = dp[0][i-1] + grid[0][i]
  }
  for i := 1; i < m; i++ {
	for j := 1; j < n; j++ {
	  dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
	}
  }
  return dp[m-1][n-1]
}

提交后发现 Runtime: 12 ms, faster than 28.57% of Go online submissions.
Memory Usage: 4.4 MB, less than 13.64% of Go online submissions for Minimum Path Sum. 效率太低了，想办法来优化下。

实际上我们只需要一个长度为n-1的一维数组来存储状态集合，状态转移的过程都可以基于这个一维数组来操作。继续上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minPathSum(grid [][]int) int {
  if grid == nil || len(grid) == 0 {
    return 0
  }
  m, n := len(grid), len(grid[0])
  dp := make([]int, n)
   
  for j, _ := range dp {
    dp[j] = math.MaxInt32
  }
  dp[0] = 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if j == 0 {
        dp[j] += grid[i][j]
      } else {
        dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
      }
    }
  }
  return dp[n-1]
}

再次提交后 Runtime: 8 ms, faster than 100.00% of Go online submissions for Minimum Path Sum.
Memory Usage: 3.9 MB, less than 59.09% of Go online submissions for Minimum Path Sum. : )

Unique Paths II(63)

63 Unique Paths II

Question

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

Now consider if some obstacles are added to the grids. How many unique paths would there be?

Example

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Analysis

第一感觉是可以用回溯来解决此问题。对每一个点先选择向右走，如果遇到障碍物或者右边无路说明此路径不通，回退到该点选择向下走，如果遇到障碍物或下边无路可走说明不存在任何一条路径可以经过该点走到终点。依次类推，每次递归向后走到终点时count加一。

需要特别注意的是要开始OR结束点值为1的情况

核心代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
func DFS(obstacleGrid [][]int, i, j int) {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    if i == m - 1 && j == n - 1  && obstacleGrid[i][j] != 1{
        count++
        return 
    }
    if i < m - 1 && obstacleGrid[i+1][j] == 0 {
        DFS(obstacleGrid, i + 1, j)
    }
    if j < n - 1 && obstacleGrid[i][j+1] == 0 {
        DFS(obstacleGrid, i, j + 1)
    }
}

递推算法基本类似于暴力求解，无重复又没有遗漏的穷举出所有走法。果不其然代码提交后TLE : (

继续分析这道题，对于图中任一个非障碍点(i,j)，从起始位置走到该点的路径个数可以通过走到该点的左边位置（i-1,j)和上方位置(i,j-1)的路径个数之和计算， 即

dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0

因此可以改用DP算法来解决，同样为了优化算法效率我们通过一个一维数组在存储状态集合，此时状态方程为
dp[i] += dp[i-1] if obstacleGrid[i][j] == 0

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    if obstacleGrid == nil || len(obstacleGrid) == 0 {
        return 0
    }
    
    m, n, count := len(obstacleGrid), len(obstacleGrid[0]), 0
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
        return count
    }
    
    dp := make([]int, n)
    dp[0] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0 
            } else {
                if j != 0 {
                    dp[j] += dp[j-1]
                }
            }
            
        }
    }
    return dp[n-1]
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Unique Paths II.
Memory Usage: 2.6 MB, less than 66.67% of Go online submissions for Unique Paths II.