Saturday, September 2, 2017

[LeetCode]Minimum Path Sum


简单的DP题,DP方程:

  • dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
假设input矩阵,高n宽m,用滚动数组可以把空间优化到O(m),时间复杂度O(m * n),代码如下:


No comments:

Post a Comment