fork download
  1. import java.util.Scanner;
  2.  
  3. class FrogJump {
  4.  
  5. public static void main(String[] args) {
  6. Scanner sc = new Scanner(System.in);
  7.  
  8. // Read number of stones and maximum jump length
  9. int n = sc.nextInt();
  10. int k = sc.nextInt();
  11.  
  12. int[] heights = new int[n];
  13.  
  14. for (int i = 0; i < n; i++) {
  15. heights[i] = sc.nextInt();
  16. }
  17.  
  18. int[] dp = new int[n];
  19.  
  20. dp[0] = 0;
  21.  
  22. for (int i = 1; i < n; i++) {
  23. dp[i] = Integer.MAX_VALUE;
  24. // Math.max(1,i-k) will give us the jump the frog starts from
  25. // i=2 means 3 elems and we curr on 3rd elem we will see all k elem before i.
  26. // dp[i] = minimum cost to REACH Stone i, not the cost of standing on Stone i.
  27. for (int j = Math.max(0, i - k); j < i; j++) {
  28. dp[i] = Math.min(dp[i],
  29. dp[j] + Math.abs(heights[i] - heights[j]));
  30. }
  31. }
  32.  
  33. System.out.println(dp[n - 1]);
  34. sc.close(); // Close the scanner
  35. }
  36. }
  37.  
Success #stdin #stdout 0.11s 54500KB
stdin
10 4
40 10 20 70 80 10 20 70 80 60
stdout
40