FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/cpp/uniquePaths/uniquePaths.cpp at master · openhardnudd/leetcode · GitHub
openhardnudd
/
leetcode
Public
forked from
haoel/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
uniquePaths
/
uniquePaths.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
87 lines (80 loc) · 2.69 KB
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
uniquePaths
/
uniquePaths.cpp
Copy path
File metadata and controls
87 lines (80 loc) · 2.69 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//
Source : https://oj.leetcode.com/problems/unique-paths/
//
Author : Hao Chen
//
Date : 2014-06-25
/*
*********************************************************************************
*
* 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).
*
*
* start
* +---------+----+----+----+----+----+
* |----| | | | | | |
* |----| | | | | | |
* +----------------------------------+
* | | | | | | | |
* | | | | | | | |
* +----------------------------------+
* | | | | | | |----|
* | | | | | | |----|
* +----+----+----+----+----+---------+
* finish
*
*
* How many possible unique paths are there?
*
* Above is a 3 x 7 grid. How many possible unique paths are there?
*
* Note: m and n will be at most 100.
*
*********************************************************************************
*/
#
include
<
stdio.h
>
#
include
<
stdlib.h
>
void
printMatrix
(
int
*a,
int
m,
int
n);
/*
* Dynamic Programming
*
* We have a dp[i][j] represents how many paths from [0][0] to hear. So, we have the following DP formuler:
*
* dp[i][j] = 1 if i==0 || j==0 //the first row/column only have 1 uniqe path.
* = dp[i-1][j] + dp[i][j-1] //the path can be from my top cell and left cell.
*/
int
uniquePaths
(
int
m,
int
n) {
int
* matrix =
new
int
[m*n];
printMatrix
(matrix, m, n);
for
(
int
i=
0
; i<m; i++){
for
(
int
j=
0
; j<n; j++){
if
(i==
0
|| j==
0
){
matrix[i*n+j]=
1
;
}
else
{
matrix[i*n+j] = matrix[(i-
1
)*n+j] + matrix[i*n+j-
1
];
}
}
}
printMatrix
(matrix, m, n);
int
u = matrix[m*n-
1
];
delete[]
matrix;
return
u;
}
void
printMatrix
(
int
*a,
int
m,
int
n)
{
for
(
int
i=
0
; i<m; i++){
for
(
int
j=
0
; j<n; j++){
printf
(
"
%4d
"
, a[i*n+j]);
}
printf
(
"
\n
"
);
}
printf
(
"
\n
"
);
}
int
main
(
int
argc,
char
** argv)
{
int
m=
3
, n=
7
;
if
( argc>
2
){
m =
atoi
(argv[
1
]);
n =
atoi
(argv[
2
]);
}
printf
(
"
uniquePaths=%d
\n
"
,
uniquePaths
(m,n));
return
0
;
}
Back
|
FazBrowse Home
|
New Git URL