120. Triangle
(0,0) -> (1,0), (1,1)
(1,0) -> (2,0), (2,1) ; (1,1) -> (2,1), (2,2) ;
(2,0) -> (3,0), (3,1) ; (2,1) -> (3,1), (3,2) ; (2,2) -> (3,2), (3,3) ;
........
sumPath[x][y] = min(dfs(x+1, y),dfs(x+1, y+1)) + traingle[x][y]
Deciding which part of the cache to discard to save space can be a hard job.
此题关键是,dfs
记录当前状态到达目标状态的耗费,记忆化搜索就是dfs
带值回来。
不仅要做DFS,还要自下而上方便存储,并且每次DFS要带值回来,dfs(x,y)
即从(x,y)
到终点的最短路径。
求最值一般可以用动态规划实现,而不是列举所有可能性。动态规划的精髓是记忆化搜索,记忆化搜索的精髓是自底而上,值可以被重复利用。
自下而上用一个list记录每一行(x,y)
的最小值,每一行迭代一次,都更新目前行的每个数据的最小值。
Last updated