文系プログラマーのプログラミング備忘録

Java、競プロ、数学などについて書いてます

Frog 1 [Educational DP Contest A]

atcoder.jp


「DPの一番簡単なやつ」です。
余談ですが、この問題、以下の問題と寸分違わず同じになっています。


C - 柱柱柱柱柱


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]);
		
}