Advertisement
Kali_prasad

count ways to reach N ,with fwd and bwd jumps

Jan 3rd, 2025 (edited)
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.37 KB | None | 0 0
  1. import java.util.*;
  2. //H means hard , R means retry , P means pending, V means view online
  3. /*
  4.  
  5. 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
  6. 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
  7. ways to reach the N from 1
  8.  */
  9.  
  10.  /*
  11.  
  12. //inputs for array
  13. 1 2 1 1 2 2 1 2
  14.  
  15. expected output -
  16. The result is
  17.  
  18.  
  19.  */
  20. @SuppressWarnings("unused")
  21. public class DpExample024 {
  22.  
  23.     static Scanner sc = new Scanner(System.in);
  24.  
  25.     private static int[] getArray() {
  26.         String[] sArr = sc.nextLine().split(" ");
  27.         int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
  28.         return arr;
  29.     }
  30.  
  31.     private static char[] getCharArray() {
  32.         String[] sArr = sc.nextLine().split(" ");
  33.         char[] cArr = new char[sArr.length];
  34.         for (int i = 0; i < sArr.length; i++) {
  35.             cArr[i] = sArr[i].charAt(0); // Take the first character of each string
  36.         }
  37.         return cArr;
  38.     }
  39.  
  40.     private static int getMax(int[] arr) {
  41.         int currMax = Integer.MIN_VALUE;
  42.         for (int curr : arr) {
  43.             currMax = Math.max(currMax, curr);
  44.         }
  45.         return currMax;
  46.     }
  47.  
  48.     public static void main(String args[]) {
  49.         // prepare the inputs
  50.  
  51.         int[] ar = getArray();
  52.  
  53.        
  54.  
  55.         int arrLen = ar.length;
  56.         //prepare the dp
  57.         int[][] dp = new int[arrLen][2];//[arrLen][0 for 0 backward jump made till i, 1 for 1 backward jump made till i]
  58.  
  59.         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
  60.         dp[0][1] = 0;//impossible to have backward jump
  61.  
  62.         dp[1][0] = dp[0][0];
  63.         dp[1][1] = 0;//impossible to do backward journey and no need to do if the size is only 2,assumed
  64.        
  65.         for (int i = 2; i < arrLen; i += 1) {
  66.             //no backward jumps
  67.             dp[i][0] = dp[i-1][0];
  68.  
  69.             if(ar[i-2]==2){
  70.                 dp[i][0] += dp[i-2][0];//you will consider ways directly through i-2 only when it is value of 2
  71.             }
  72.  
  73.  
  74.             //one backward jump
  75.             dp[i][1] = dp[i-1][1];//backward jump happened in past when coming from i-1 journey  
  76.                      
  77.             if(ar[i-2]==2){
  78.                 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
  79.                 if((i-3)>=0 && ar[i-3]==2){
  80.                     dp[i][1] += dp[i-3][0];//no back jumps happened till now , the only possible journey will something look like
  81.                     /* from i-3 +2 front jump to i-1
  82.                        from i-1 -1 back jump to i-2
  83.                        from i-2 +2 jump to i //this is only possible way to have a back jump in i-1 and i-2
  84.  
  85.                        if
  86.                        from i-3 +1 front jump to i-2 jump
  87.                        from i-2 you cannot do smallest back jump such that you can reach i in future
  88.                        so starting method is the only way
  89.                     */
  90.                 }
  91.             }
  92.  
  93.            
  94.  
  95.  
  96.            
  97.         }
  98.         int res = dp[arrLen-1][0]+dp[arrLen-1][1];
  99.         System.out.println("The result is " + res);
  100.  
  101.     }
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement