forked from the-moonLight0/Hactober-fest-2021
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ok3.java
97 lines (90 loc) · 1.88 KB
/
ok3.java
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
88
89
90
91
92
93
94
95
96
97
//left , down and diagonal are allowed memorization
public static int Paths2(int sx,int sy,int ex,int ey,int[][] dp) {
if(sx==ex && sy==ey) {
return 1;
}
int count=0;
if(dp[sx][sy]!=0) {
return dp[sx][sy];
}
if(sx+1<=ex) {
count+=Paths2(sx+1,sy,ex,ey,dp);
}
if(sy+1<=ey) {
count+=Paths2(sx,sy+1,ex,ey,dp);
}
if(sy+1<=ey && sx+1<=ex) {
count+=Paths2(sx+1,sy+1,ex,ey,dp);
}
dp[sx][sy]=count;
return count;
}
//left , down and diagonal are allowed tabulation
public static int Paths2T(int sx,int sy,int ex,int ey,int[][] dp) {
for(sx=ex;sx>=0;sx--) {
for(sy=ey;sy>=0;sy--) {
if(sx==ex && sy==ey) {
dp[sx][sy]=1;
continue;
}
int count=0;
if(sx+1<=ex) {
count+=dp[sx+1][sy];
}
if(sy+1<=ey) {
count+=dp[sx][sy+1];
}
if(sy+1<=ey && sx+1<=ex) {
count+=dp[sx+1][sy+1];
}
dp[sx][sy]=count;
}
}
return dp[0][0];
}
//left and down moves are allowed in jumps
public static int Paths3(int sx,int sy,int ex,int ey,int[][] dp) {
if(sx==ex && sy==ey) {
return 1;
}
if(dp[sx][sy]!=0) {
return dp[sx][sy];
}
int count=0;
for(int i=1;i<=ex;i++) {
if(sx+i<=ex) {
count+=Paths3(sx+i,sy,ex,ey,dp);
}
}
for(int i=1;i<=ey;i++) {
if(sy+i<=ey ) {
count+=Paths3(sx,sy+i,ex,ey,dp);
}
}
dp[sx][sy]=count;
return count;
}
//left and down moves are allowed in jumps tabulation
public static int Paths3T(int sx,int sy,int ex,int ey,int[][] dp) {
for(sx=ex;sx>=0;sx--) {
for(sy=ey;sy>=0;sy--) {
if(sx==ex && sy==ey) {
dp[sx][sy]=1;
continue;
}
int count=0;
for(int i=1;i<=ex;i++) {
if(sx+i<=ex) {
count+=dp[sx+i][sy];
}
}
for(int i=1;i<=ey;i++) {
if(sy+i<=ey ) {
count+=dp[sx][sy+i];
}
}
dp[sx][sy]=count;
}
}
return dp[0][0];
}