Being hooked on something makes you strong

I watched a TV drama entitled "aibou," which means buddy, co-worker or that kind of thing in Japanese, on this new year's day.

On the drama, a wife who had lost her son by a traffic accident, made explosive bombs and revenged on someone who killed her son.

On the drama, a detective, who solved the case, said "You think that an average house wife cannot make bombs, right? But one can do anything if s/he tries it all out."

And he continued, "She became really keen on studying about bomb. It made her proactive, outgoing and lively. Even though she stayed up late in the night -- 2 or 3 AM -- every day, she never looked sleepy. She looked cheerful every day."

あれ、何か。前置きが長くなった。

まー要約すると、最近仕事が忙しいことを言い訳にしてアルゴリズムの勉強をサボりがちだったけど、それは違うなと思いました。

本当に好きなこと、本当にやるべきことであれば、寝る時間を削ってでもやるべきだと。

そして、その方が活力的な生活が送れるはずだと信じています。

って、こんな精神論を書きたいわけじゃなかったのですが、

今日は、中国語の問題を解きました。

http://poj.org/problem?id=1664

ちょっと文章が分かり難いですが、要は、

「mをn個以下に分割するパターンを求めよ。」

です。

分割数は、動的計画で解くのが定石。

分割数を知らない人はこのページを見よう！！

http://techtipshoge.blogspot.com/2011/01/blog-post_28.html

これくらいの規模ならDFSとかで解けそうですが、入力サイズが大きくなると動的計画じゃないと厳しそうです。。

int dp[16][16];

void init() {
   REP(i, 16)
       dp[i][0] = 0, dp[0][i] = 1;
   dp[0][0] = 1;

   FOR (i, 1, 16) FOR (j, 1, 16) {
       if (i-j >= 0)
           dp[i][j] = dp[i][j-1] + dp[i-j][j];
       else
           dp[i][j] = dp[i][j-1];
   }
}

int main() {
   int t, n, m;

   init();
   scanf("%d", &t);
   REP(i, t) {
       scanf("%d %d", &n, &m);
       printf("%d\n", dp[n][m]);
   }

   return 0;
}