-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNCR.java
More file actions
31 lines (30 loc) · 878 Bytes
/
NCR.java
File metadata and controls
31 lines (30 loc) · 878 Bytes
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
import java.util.Arrays;
import java.util.Scanner;
public class NCR {
static int dp[][];
static int calculateNcrRec(int n, int r) {
if(r == 0) return 1;
else if(r==1) return n;
else if(dp[r][n] !=-1) return dp[r][n];
else {
int t = dp[r][n-1], t1 = dp[n-1][r-1];
if(t ==-1) {
t = calculateNcrRec(n-1,r);
}
if(t1 == -1) {
t1 = calculateNcrRec(n-1, r-1);
}
dp[r][n] = t + t1;
return dp[r][n];
}
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int r = sc.nextInt();
dp = new int[r+1][n+1];
for(int a[]: dp) Arrays.fill(a,-1);
if(r > n-r) r = n-r;
System.out.println(calculateNcrRec(n, r));
}
}