fork download
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5. public static void main(String[] args) {
  6. Scanner scanner = new Scanner(System.in);
  7. int n = scanner.nextInt();
  8.  
  9. int[] b = new int[n + 1];
  10. for (int i = 1; i <= n; i++) {
  11. b[i] = scanner.nextInt();
  12. }
  13.  
  14. int[][] dp = new int[n + 1][5];
  15. // rech first pos forwaard only
  16. dp[1][1] = b[1];
  17. // cant rech first index with back jump from 2nd
  18. // its alr visited
  19. dp[1][2] = Integer.MAX_VALUE;
  20. // CANT REACH 2ND POS WITH forward jumps
  21. dp[2][1] = Integer.MAX_VALUE;
  22. // take cost to reach dp[i-1][1] that is the forward jumps to reach i-1
  23. // b[3] taken coz we alr need to be at 3 if we can get to 2, IMP :: and the cost at b[3] is dp[1][1]
  24. // that is forward jumps from dp[i-1][1] since that forward jump from i-1 to i+1 is what lets us be at i + 1
  25. // finally take the back jump from i+1.. this is the cost of being at i coming from back jump
  26. dp[2][2] = b[3] + b[2] + dp[1][1];
  27.  
  28. int i = 3;
  29. while (i <= n-1) {
  30. dp[i][1] = b[i] + Math.min(dp[i - 2][1], dp[i - 2][2]);
  31. dp[i][2] = b[i] + b[i + 1] + dp[i - 1][1];
  32. i++;
  33. }
  34. //At n-1 point, the loop has calculated: dp[n-1][1], dp[n-1][2]
  35. // now for n, we cant come back to n .. either we reach n or we can skip n
  36. // if we reached n-1 thru back and took n value then we jump straight out
  37. //take min of
  38. dp[i][2] = b[n] + Math.min(dp[i-2][2],dp[i-2][1]);
  39. dp[i][1] = 100000000 ;
  40. int ans = Math.min(
  41. dp[n][2],
  42. Math.min(dp[n - 1][1], dp[n - 1][2])
  43. );
  44. System.out.print(ans);
  45. }
  46. }
  47.  
Success #stdin #stdout 0.11s 45884KB
stdin
3
2 5 8
stdout
10