[LintCode/LeetCode] Unique Paths

Gu_Yan 发布于2019-08-14 15:27 / 2732人阅读

摘要：简单的动规题目，建立数组。坐标为矩阵的坐标，值为从左上角到这一格的走法总数。赋初值，最上一行和最左列的所有格子的走法都只有一种，其余格子的走法等于其左边格子走法与上方格子走法之和。最后，返回即可。

Problem

A robot is located at the top-left corner of a m x n grid (marked "Start" in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked "Finish" in the diagram below).

How many possible unique paths are there?

Note

简单的动规题目，建立dp数组。dp[i][j]坐标为矩阵的坐标，值为从左上角到这一格的走法总数。赋初值，最上一行和最左列的所有格子的走法都只有一种，其余格子的走法等于其左边格子走法与上方格子走法之和。最后，返回dp[m-1][n-1]即可。

Solution

二维DP

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

一维DP

public class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
}

云服务器 GPU云服务器 Paths unique Mysql_unique array_unique

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65769.html

[LintCode/LeetCode] Unique Paths II

摘要：和完全一样的做法，只要在初始化首行和首列遇到时置零且即可。对了，数组其它元素遇到也要置零喏，不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 评论0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 评论0 收藏0
[LintCode/LeetCode] 3Sum

摘要：双指针法的解法。然后用和夹逼找到使三数和为零的三数数列，放入结果数组。对于这三个数，如果循环的下一个数值和当前数值相等，就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

Sunxb 2019-08-14 15:42 评论0 收藏0