leetcode 64. Minimum Path Sum DP动态规划

逃离我推掉我的手 2022-06-09 11:42 150阅读 0赞

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

和上一道题[leetcode 62. Unique Paths][] 和 [ leetcode 63. Unique Paths II][leetcode 63. Unique Paths II] 一模一样，不过这里求的是最小的路径之和。

代码如下：

public class Solution 
    {
        /*
         * 这个和之前的动态规划方法很类似，
         * */
        public int minPathSum(int[][] mat) 
        {
            //特殊情况
            if(mat==null || mat.length<=0)
                return 0;
    
            int [][]vis=new int[mat.length][mat[0].length];
            vis[0][0]=mat[0][0];
    
            //动态规划的第一行和第一列的初始化，注意要累积权重值
            for(int i=1;i<mat.length;i++)
                vis[i][0]=vis[i-1][0]+mat[i][0];
            for(int i=1;i<mat[0].length;i++)
                vis[0][i]=vis[0][i-1]+mat[0][i];
    
            //每一次更新最小的值
            for(int i=1;i<mat.length;i++)
            {
                for(int j=1;j<mat[0].length;j++)
                    vis[i][j]=Math.min(vis[i-1][j],vis[i][j-1])  +  mat[i][j];
            }
            return vis[mat.length-1][mat[0].length-1];
        }
    }

和上面的体基本保持一致，就是一个DP的简单应用

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int minPathSum(vector<vector<int>>& gg) 
        {
            if (gg.size() <= 0)
                return 0;
            vector<vector<int>> dp = gg;
            for (int i = 1; i < gg.size(); i++)
                dp[i][0] = dp[i-1][0] + gg[i][0];
            for (int i = 1; i < gg[0].size(); i++)
                dp[0][i] = dp[0][i - 1] + gg[0][i];
    
            for (int i = 1; i < gg.size(); i++)
            {
                for (int j = 1; j < gg[0].size(); j++)
                {
                    dp[i][j] = gg[i][j] + min(dp[i-1][j], dp[i][j-1]);
                }
            }
            return dp[dp.size() - 1][dp[0].size() - 1];
        }
    };

[leetcode 62. Unique Paths]: http://blog.csdn.net/jackzhang_123/article/details/77848042
[leetcode 63. Unique Paths II]: http://blog.csdn.net/jackzhang_123/article/details/77848464