摘要:簡單的動規題目,建立數組。坐標為矩陣的坐標,值為從左上角到這一格的走法總數。賦初值,最上一行和最左列的所有格子的走法都只有一種,其余格子的走法等于其左邊格子走法與上方格子走法之和。最后,返回即可。
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]; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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