思路
dp：代表到达当前位置的总方式
初始化：第一行的位置dp[0][j]：当前位置只能由左边的位置向右移动得到 所以只有1种方式 d[0][j]=1, d[0][0]=1
第一列的位置 dp[i][0]：当前位置只能由上一个位置向下移动得到
除此之外的位置可以由上方位置向下移动或者左边位置向右移动得到 即dp[i][j]=dp[i-1][j]+dp[i][j-1] (画二维数组就比较容易理解了）
时间复杂度: O(M∗N)
class Solution(object):def uniquePaths(self, m, n):""":type m: int:type n: int:rtype: int"""dp =[]for i in range(m):t = []for j in range(n):if i ==0:t.append(1)else:if j == 0:t.append(1)else:t.append(t[j-1]+dp[i-1][j])dp.append(t)return dp[m-1][n-1]
与上面的解题思路是一样的
思路
dp代表路径总和
grid可以理解为每个位置权重（下面写的用权重来表示）
初始化：
dp[0][0]=grid[0][0
第一行位置dp[0][j]：
每个位置可由左边位置向右移动得到 所以当前位置数字总和=左边位置权重+当前位置权重
第一列数据 dp[i][0]:
每个位置可由上方位置向下移动得到 所以当前位置数字总和=上方位置权重+当前位置权重
此外位置：
除此之外的位置可以由上方位置向下移动或者左边位置向右移动得到 所以比较上方、左边位置权重，哪个最小就由哪个移动到当前位置
t[j-1]：即为 dp[i][j-1], 用t[j-1]来表示的原因：往dp添加数据是一行一行来添加的，此时t还未添加到dp里，dp里是没有dp[i][j-1]
class Solution(object):def minPathSum(self, grid):""":type grid: List[List[int]]:rtype: int"""dp = []for i in range(len(grid)):t=[]for j in range(len(grid[i])):if i == 0:if j == 0:t.append(grid[i][j])else:t.append(grid[i][j]+t[j-1])else:if j == 0:t.append(grid[i][j]+dp[i-1][j])else:s = min(dp[i-1][j],t[j-1]) +grid[i][j]t.append(s)dp.append(t)return dp[-1][-1]
