Given a matrix, get the number of path from the top left cell to the top right cell.
Note that: you can only go right, up right, down right.
|
(0,0) |
(0,1) |
(0,2) |
(0,3) |
(0,4) |
|
(1,0) |
(1,1) |
(1,2) |
(1,3) |
(1,4) |
|
(2,0) |
(2,1) |
(2,2) |
(2,3) |
(2,4) |
|
(3,0) |
(3,1) |
(3,2) |
(3,3) |
(3,4) |
sol1: DFS
(0,0)
9
/ur |r \dr
(-1,1) (0,1) (1,1)
0 4 5
/ur |r \dr /ur |r \dr
(-1,2) (0,2) (1,2) (0,2) (1,2) (2,2)
0 2 2 2 2 1
/ | \ / | \ / | \ / | \ / | \
(-1,3)(0,3)(1,3) (0,3)(1,3)(2,3) (-1,3)(0,3)(1,3) (0,3)(1,3)(2,3) (1,3)(2,3)(3,3)
0 1 1 1 1 0 0 1 1 1 1 0 1 0 0
/ | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \
010 100 010 100000 010 100 010 100 000 100 000 00 0
Each node is a sub problem: the number of path from the cell (x,y) to (0,4)
branching factor: 3
base case: (x,y) out of bound, / y = col - 1
Time: O(3^n * 1)
Space: O(n) n = col
sol2: DFS + memorization
We can notice that, some sub problem, ie. the node with the same cell pair, is calculated multiple times.
So when we calculate it the first time, we memorize the result of this sub problem.
memo[i][j] the number of path from (i,j) to (0,4)
(0,0) (3,4) 4*5
Time: O(col* row * 1)
Space:O(col) + O(col*row)
|
public int DFSwithMemo(int x, int y, int row, int col, int[][] memo) { |
sol3: DP
dp定义: dp[i][j] the number of path from (i,j) to (0,4)
induction rule: dp[i][j] = dp[i-1][j+1] + dp[i][j+1]+dp[i+1][j+1]
base case: dp[0][4] = 1, dp[i][4] = 0 i != 0
i < 0 || i > row - 1 || y < 0 || y> col - 1 dp[i][j] = 0
result: dp[0][0]
Space:O(row*col)
从右向左
2 4
2 4
1 3
0 1
O(row * 2)
4*5 0
x x 2 1 1
x x x 1 0
x x x 0 0
x x x 0 0
2 0
2
1
0
x x 2 1 1
x x x 1 0
x x x 0 0
x x x 0 0
|
(0,0) |
(0,1) |
(0,2) |
(0,3) |
(0,4) |
|
(1,0) |
(1,1) |
(1,2) |
(1,3) |
(1,4) |
|
(2,0) |
(2,1) |
(2,2) |
(2,3) |
(2,4) |
|
(3,0) |
(3,1) |
(3,2) |
(3,3) |
(3,4) |
dp定义: dp[i][j] the number of path from (0,0) to (i,j)
induction rule: dp[i][j] = dp[i-1][j-1] + dp[i][j-1]+dp[i+1][j-1]
base case: dp[0][0] = 1, dp[i][0] = 0 i != 0
i < 0 || i > row - 1 || y < 0 || y> col - 1 dp[i][j] = 0
result: dp[0][4]
Time: O(col * row * 1)
Space:O(col * row)
""
Follow up 1: What if you are required to go below the line
|
(0,0) |
(0,1) |
(0,2) |
(0,3) |
(0,4) |
|
(1,0) |
(1,1) |
(1,2) |
(1,3) |
(1,4) |
|
(2,0) |
(2,1) |
(2,2) |
(2,3) |
(2,4) |
|
(3,0) |
(3,1) |
(3,2) |
(3,3) |
(3,4) |
Follow up 2: What if you are required to use the cell (1,1)
Follow up 3: What if there are some blocked cell
Given a matrix, get the number of path from the top left cell to the top right cell.
原文：https://www.cnblogs.com/tobeabetterpig/p/9741349.html