[LeetCode]64. 最小路径和(DP)

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

最常规的二维dp数组维护。

代码

public class Solution {

    public int minPathSum(int[][] grid) {

        int[][] dp=new int[grid.length][grid[0].length];

        dp[0][0]=grid[0][0];

        for(int j=1;j<grid[0].length;++j){

            dp[0][j]=dp[0][j-1]+grid[0][j];

        }

        for(int i=1;i<grid.length;++i){

            dp[i][0]=dp[i-1][0]+grid[i][0];

        }

        for(int i=1;i<grid.length;++i){

            for(int j=1;j<grid[0].length;++j){

                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];

            }

        }

        return dp[grid.length-1][grid[0].length-1];

    }

}

巴特西

[LeetCode]64. 最小路径和(DP)

题目

题解

代码

最新文章

热门文章