FilesExpand file tree

 master

/

BoardPath.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (70 loc) · 1.57 KB

 master

/

BoardPath.java

Top

File metadata and controls

• Code
• Blame

77 lines (70 loc) · 1.57 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

package DynamicProgramming;

/*

* this is an important Algo in which

* we have starting and ending of board and we have to reach

* we have to count no. of ways

* that help to reach end point i.e number by rolling dice

* which have 1 to 6 digits

Test Case:

here target is 10

int n=10;

startAlgo();

System.out.println(bpR(0,n));

System.out.println(endAlgo()+"ms");

int[] strg=new int [n+1];

startAlgo();

System.out.println(bpRS(0,n,strg));

System.out.println(endAlgo()+"ms");

startAlgo();

System.out.println(bpIS(0,n,strg));

System.out.println(endAlgo()+"ms");

*/

public class BoardPath {

public static long startTime;

public static long endTime;

public static void startAlgo() {

startTime=System.currentTimeMillis();

}

public static long endAlgo() {

endTime=System.currentTimeMillis();

return endTime-startTime;

}

public static int bpR(int start,int end){

if(start==end) {

return 1;

}

else if(start>end)

return 0;

int count=0;

for(int dice=1;dice<=6;dice++) {

count+=bpR(start+dice,end);

}

return count;

}

public static int bpRS(int curr,int end,int strg[]){

if(curr==end) {

return 1;

}

else if(curr>end)

return 0;

if(strg[curr]!=0)

return strg[curr];

int count=0;

for(int dice=1;dice<=6;dice++) {

count+=bpRS(curr+dice,end,strg);

}

strg[curr]=count;

return count;

}

public static int bpIS(int curr,int end,int[]strg){

strg[end]=1;

for(int i=end-1;i>=0;i--) {

int count=0;

for(int dice=1;dice<=6&&dice+i<strg.length;dice++) {

count+=strg[i+dice];

}

strg[i]=count;

}

return strg[0];

}

}