摘要:简单的动规题目,建立数组。坐标为矩阵的坐标,值为从左上角到这一格的走法总数。赋初值,最上一行和最左列的所有格子的走法都只有一种,其余格子的走法等于其左边格子走法与上方格子走法之和。最后,返回即可。
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]; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65769.html
摘要:和完全一样的做法,只要在初始化首行和首列遇到时置零且即可。对了,数组其它元素遇到也要置零喏,不过就不要啦。 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...
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...
摘要:和唯一的不同是组合中不能存在重复的元素,因此,在递归时将初始位即可。 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...
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...
摘要:双指针法的解法。然后用和夹逼找到使三数和为零的三数数列,放入结果数组。对于这三个数,如果循环的下一个数值和当前数值相等,就跳过以避免中有相同的解。 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...
阅读 2089·2021-11-23 09:51
阅读 3697·2021-10-20 13:49
阅读 1706·2021-09-06 15:13
阅读 1816·2021-09-06 15:02
阅读 3154·2021-09-02 15:11
阅读 890·2019-08-29 15:37
阅读 1732·2019-08-29 13:24
阅读 2274·2019-08-29 11:28