FilesExpand file tree

 master

/

BoardPath.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (65 loc) · 1.73 KB

 master

/

BoardPath.java

Top

File metadata and controls

• Code
• Blame

75 lines (65 loc) · 1.73 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

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];

}

}