動的計画法
動的計画法（dynamic programming，DP）の問題はAtCoderでも多数出題されています。その最初のカエル🐸の問題を考えてみましょう。 $ N 個の足場があります。足場には $ 1,2,\ldots,N と番号が振られています。各 $ i $ (1 \leq i \leq N) について、足場 $ i の高さは $ h_i です。
最初、足場 1 にカエルがいます。カエルは次の行動を何回か繰り返し、足場 $ N まで辿り着こうとしています。
・足場 $ i にいるとき、足場 $ i+1 または $ i+2 へジャンプする。このとき、ジャンプ先の足場を $ j とすると、コスト $ |h_i - h_j| を支払う。
カエルが足場 $ N に辿り着くまでに支払うコストの総和の最小値を求めてください。
入力はすべて整数で $ 2 \leq N \leq 10^5，$ 1 \leq h_i \leq 10^4 です。コストの総和はたかだか $ 10^9 ですので，$ 2 \times 10^9 までの値を表すことができる int 型で大丈夫です。
カエルの経路は $ N が増えると指数関数的に増えてしまいます。しかし，足場 $ i-1 までの答えがわかっていれば，足場 $ i の答えは漸化式で簡単に求めることができます。これが動的計画法の考え方です。
具体的には次のような感じです（abs を使うために stdlib.h をインクルードする必要があります）。
code:test.c
for (i = 2; i < n; i++) {
if (a < b)
else
}
これを参考にして正しく動作するプログラムを作ってください。
（実は cost[] という配列は使わなくてもできます。どうすればいいでしょうか。）
上のプログラムは最小のコストしか出力しません。どういうふうに足場をたどればコストが最小になるかも出力するようにしてみてください。
あと，比較のため，再帰を使ったプログラムも作ってみてください。DPと比べてどの程度の計算時間がかかるでしょうか。
DPでよく出される問題の一つに最長共通部分列（LCS）問題があります。解説とPythonで実装した例が私の最長共通部分列問題のページにありますので参考にしてC言語で書いてみてください。