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 でも解けるらしいけどもっとわからん。