Frog 1 [Educational DP Contest A]
「DPの一番簡単なやつ」です。
余談ですが、この問題、以下の問題と寸分違わず同じになっています。
void solve () { int n = nextInt(); int[] ar = nextIntArray(n); int[] dp = new int[n]; dp[0] = 0; dp[1] = Math.abs(ar[1]-ar[0]); for (int i=2; i<n; i++) { dp[i] = Math.min(dp[i-1]+Math.abs(ar[i]-ar[i-1]), dp[i-2]+Math.abs(ar[i]-ar[i-2])); } out.println(dp[n-1]); }