Leetcode--出界的路径数

给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109 + 7 的值。

示例 1：

输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6
解释:

示例 2：

输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12
解释:

说明:

球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。

思路：

1.非法的坐标不是被弃之不理，而是把上一步当前位置的元素代表的可能数加到结果的总个数中，并且此题dp数组每个元素存的不是走到这里的概率，而是走到这里的可能总路径数。注意在运算过程要取模。

def findPaths(self, m, n, N, i, j):""":type m: int:type n: int:type N: int:type i: int:type j: int:rtype: int"""if N == 0:return 0lastStepCount = [[0 for i in range(n)] for j in range(m)]   #对之前坐标进行遍历move = [[0, 1], [1, 0], [0, -1], [-1, 0]]    #一次只能移动一个上下左右lastStepCount[i][j] = 1        #初始化定义res, mod = 0, 1000000007     for step in range(1, N + 1):       currCount = [[0 for i in range(n)] for j in range(m)]    #正则表达式循环现在的坐标for x in range(m):for y in range(n):for direction in move:									lastX, lastY = x + direction[0], y + direction[1]		#对坐标进行位置移动if any([lastX < 0, lastX >= m, lastY < 0, lastY >= n]):     res = (res + lastStepCount[x][y]) % mod      #如果出界了，就直接求出结果else:   		#否则就继续迭移动currCount[x][y] = (currCount[x][y] + lastStepCount[lastX][lastY]) % modlastStepCount = currCount     #重新赋值return res

时间复杂度O(N * m * n)

2.从坐标[i, j]到其上、下、左、右都需要移动1步，剩余N-1步，那么问题转化为从上、下、左、右移动N-1步，一共有多少种方法。

class Solution:def findPaths(self, m, n, N, i, j):""":type m: int:type n: int:type N: int:type i: int:type j: int:rtype: int"""tmp=[[[0 for i in range(n)] for j in range(m)] for k in range(N+1)]  #坐标和移动次数的三维数组for k in range(1,N+1):																			for p in range(m):				for q in range(n):					if 0==p:						#如果横坐标是0up=1								#就可以向上走else:up=tmp[k-1][p-1][q]			#否则下就要走N-1步if m-1==p:								#如果横坐标已经是下移动1了，那么相当于已经向下走了1down=1else:down=tmp[k-1][p+1][q]		#否则就是横坐标+1的地方走N-1步if 0==q:left=1else:left=tmp[k-1][p][q-1]						#同理左右也是一样if n-1==q:right=1else:right=tmp[k-1][p][q+1]tmp[k][p][q]=(up+down+left+right)%1000000007   #注意最后的结果要mod那个数return tmp[N][i][j]

时间复杂度是O(N * m * n)
其实这两种方法大体上都是一样的，都是想要求到上一步的情况，那么就直接用DP状态转移来进行递归。