给定一个矩阵matrix，从左上角走到右下角。
每一个格子都包含了一个值,所以每条路径都有一个值,找到所有值不同的路径的和。
dp[i][j]表示从（i，j）走到右下角所有情况的“路径和”，用集合来表示。
递推公式：dp[i][j] = set ( [ (obj + matrix[i][j] ) for obj in union( dp[i][j+1], dp[i+1][j] ) ] )
1 class Solution: 2 """ 3 @param: : an array of arrays 4 @return: the sum of all unique weighted paths 5 """ 6 7 def uniqueWeightedPaths(self, grid): 8 # write your codes here 9 if not grid or not grid[0]: 10 return 0 11 12 dp = [set() for i in range(len(grid[0]))] 13 dp[len(grid[0]) - 1].add(0) 14 15 for row in range(len(grid) - 1, -1, -1): 16 for col in range(len(grid[0]) - 1, -1, -1): 17 if col + 1 < len(grid[0]): 18 dp[col] = dp[col].union(dp[col + 1]) 19 dp[col] = set([(obj + grid[row][col]) for obj in dp[col]]) 20 21 return sum(dp[0])
原文：https://www.cnblogs.com/liqiniuniu/p/10601250.html