题解 | #矩阵的最小路径和#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int rows,cols;
    public int minPathSum (List<List<int>> matrix) {
        // write code here
        rows=matrix.Count;
        cols=matrix[0].Count;
        Dictionary<string, int> map=new Dictionary<string, int>();
        return minPathSum(matrix, rows-1, cols-1,  map);
    }
    public int minPathSum(List<List<int>> grid,int i,int j,Dictionary<string, int> map)
    {
        if(i==0 && j==0)
            return grid[i][j];
        string key=i+"*"+j;
        if(map.ContainsKey(key))
            return map[key];
        int res=0;
        if(i==0)
            res=grid[i][j]+minPathSum(grid, i, j-1,  map);
        else if(j==0)
            res=grid[i][j]+minPathSum(grid, i-1, j, map);
        else
            res=grid[i][j]+Math.Min(minPathSum(grid, i, j-1, map),minPathSum(grid, i-1, j, map));
        map.Add(key,res);
        return res;
    }

   
}

虽然是递归算法，但是容易理解，
1.两边缘的点是直接求得的，然后就可以求得与两边缘相邻的点，依次扩散，只是递归是倒过来的
2.为了避免大量重复计算，这里用了一个map，来临时存储