動的計画法
動的計画法（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[] という配列は使わなくてもできます。どうすればいいでしょうか。）
上のプログラムは最小のコストしか出力しません。どういうふうに足場をたどればコストが最小になるかも出力するようにしてみてください。
解答例：path[] という配列に一つ前の番号を入れていき、それを逆にたどります。結果は逆向きに出力されます。
code:test1.c
path0 = -1; /* 足場0の一つ前は存在しないので-1にしておく */ path1 = 0; /* 足場1の一つ前は足場0 */ for (i = 2; i < n; i++) {
if (a < b) {
} else {
}
}
i = n - 1;
while (i >= 0) {
printf("%d ", i);
}
printf("\n");
結果が逆向きに出力されるのがまずければ、結果をいったん別の配列に格納し、その配列を逆向きに出力すればいいでしょう。あるいは、次のような関数を定義しておき、showpath(path, n-1); と呼び出すという手もあります：
code:test3.c
void showpath(int path[], int i)
{
if (i > 0) showpath(path, pathi); printf("%d ", i);
}
DPでよく出される問題の一つに最長共通部分列（LCS）問題があります。解説とPythonで実装した例が私の最長共通部分列問題のページにありますので参考にしてC言語で書いてみてください。