資訊專欄INFORMATION COLUMN
摘要：簡(jiǎn)單的動(dòng)規(guī)題目，建立數(shù)組。坐標(biāo)為矩陣的坐標(biāo)，值為從左上角到這一格的走法總數(shù)。賦初值，最上一行和最左列的所有格子的走法都只有一種，其余格子的走法等于其左邊格子走法與上方格子走法之和。最后，返回即可。
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簡(jiǎn)單的動(dòng)規(guī)題目，建立dp數(shù)組。dp[i][j]坐標(biāo)為矩陣的坐標(biāo)，值為從左上角到這一格的走法總數(shù)。賦初值，最上一行和最左列的所有格子的走法都只有一種，其余格子的走法等于其左邊格子走法與上方格子走法之和。最后，返回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];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65769.html
摘要：和完全一樣的做法，只要在初始化首行和首列遇到時(shí)置零且即可。對(duì)了，數(shù)組其它元素遇到也要置零喏，不過就不要啦。 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...
摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。 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...
摘要：雙指針法的解法。然后用和夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過以避免中有相同的解。 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...
閱讀 2126·2021-11-23 09:51
閱讀 3712·2021-10-20 13:49
閱讀 1718·2021-09-06 15:13
閱讀 1828·2021-09-06 15:02
閱讀 3181·2021-09-02 15:11
閱讀 899·2019-08-29 15:37
閱讀 1744·2019-08-29 13:24
閱讀 2283·2019-08-29 11:28
