AOJ0030: Sum of Integers

Sum of Integers | Aizu Online Judge
深さ優先探索の問題。C++ で書いたものを Python に翻訳して分かった気になるアレ。

#!/usr/bin/env python

def dfs(pos, t, sum):
    global cnt
    if t == n:
        if sum == s:
            cnt += 1
        return
    if pos > 9:
        return
 
    dfs(pos+1, t, sum)
    dfs(pos+1, t+1, sum + pos)
 
 
while True:
    n, s = map(int, raw_input().split())
    if n==0 and s==0: break
 
    cnt = 0
    dfs(0, 0, 0)
    print cnt

蟻本の DFS の説明の理解に時間がかかったし、遷移の仕方が直感的にわからないから演習を詰むしかなさそう。
DP でも解けるらしいけどもっとわからん。