fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class FrogJump {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.  
  7.         // Read number of stones
  8.         int n = sc.nextInt();
  9.         int[] heights = new int[n + 1]; // heights array, 1-based indexing
  10.  
  11.         // Read heights of the stones
  12.         for (int i = 1; i <= n; i++) {
  13.             heights[i] = sc.nextInt();
  14.         }
  15.  
  16.         // DP array to store minimum costs
  17.         int[] dp = new int[n + 1];
  18.  
  19.         // Base cases
  20.         dp[1] = 0; // Cost to reach the first stone is 0
  21.         if (n > 1) {
  22.             dp[2] = Math.abs(heights[2] - heights[1]); // Cost to jump to the second stone
  23.         }
  24.  
  25.         // Fill the dp array
  26.         for (int i = 3; i <= n; i++) {
  27.             int jumpFromOneBack = dp[i - 1] + Math.abs(heights[i] - heights[i - 1]);
  28.             int jumpFromTwoBack = dp[i - 2] + Math.abs(heights[i] - heights[i - 2]);
  29.             dp[i] = Math.min(jumpFromOneBack, jumpFromTwoBack);
  30.         }
  31.  
  32.         // The answer is the minimum cost to reach the last stone
  33.         System.out.println(dp[n]);
  34.  
  35.         sc.close(); // Close the scanner
  36.     }
  37. }
  38.  
Success #stdin #stdout 0.11s 56564KB
comments (?)
stdin
copy 
4
10 30 40 20
stdout
copy 
30
https://ideone.com/xxrtl2
language:
Java (HotSpot 12)
created:
23 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!