Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- //H means hard , R means retry , P means pending, V means view online
- /*
- given an array containing 1 or 2 , if you are on i you can make a jump of size ar[i] forward or backward , please note that
- you can visit each index only once and through out the journey the backward jump is allowed only once . task is to count the number of
- ways to reach the N from 1
- */
- /*
- //inputs for array
- 1 2 1 1 2 2 1 2
- expected output -
- The result is
- */
- @SuppressWarnings("unused")
- public class DpExample024 {
- static Scanner sc = new Scanner(System.in);
- private static int[] getArray() {
- String[] sArr = sc.nextLine().split(" ");
- int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
- return arr;
- }
- private static char[] getCharArray() {
- String[] sArr = sc.nextLine().split(" ");
- char[] cArr = new char[sArr.length];
- for (int i = 0; i < sArr.length; i++) {
- cArr[i] = sArr[i].charAt(0); // Take the first character of each string
- }
- return cArr;
- }
- private static int getMax(int[] arr) {
- int currMax = Integer.MIN_VALUE;
- for (int curr : arr) {
- currMax = Math.max(currMax, curr);
- }
- return currMax;
- }
- public static void main(String args[]) {
- // prepare the inputs
- int[] ar = getArray();
- int arrLen = ar.length;
- //prepare the dp
- int[][] dp = new int[arrLen][2];//[arrLen][0 for 0 backward jump made till i, 1 for 1 backward jump made till i]
- dp[0][0] = 1;//assume if the size is only one then you are considered you still have one way to reach final index from starting
- dp[0][1] = 0;//impossible to have backward jump
- dp[1][0] = dp[0][0];
- dp[1][1] = 0;//impossible to do backward journey and no need to do if the size is only 2,assumed
- for (int i = 2; i < arrLen; i += 1) {
- //no backward jumps
- dp[i][0] = dp[i-1][0];
- if(ar[i-2]==2){
- dp[i][0] += dp[i-2][0];//you will consider ways directly through i-2 only when it is value of 2
- }
- //one backward jump
- dp[i][1] = dp[i-1][1];//backward jump happened in past when coming from i-1 journey
- if(ar[i-2]==2){
- dp[i][1] += dp[i-2][1];//you will consider ways directly,with single backward jump in its past, through i-2 only when it is value of 2
- if((i-3)>=0 && ar[i-3]==2){
- dp[i][1] += dp[i-3][0];//no back jumps happened till now , the only possible journey will something look like
- /* from i-3 +2 front jump to i-1
- from i-1 -1 back jump to i-2
- from i-2 +2 jump to i //this is only possible way to have a back jump in i-1 and i-2
- if
- from i-3 +1 front jump to i-2 jump
- from i-2 you cannot do smallest back jump such that you can reach i in future
- so starting method is the only way
- */
- }
- }
- }
- int res = dp[arrLen-1][0]+dp[arrLen-1][1];
- System.out.println("The result is " + res);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement