プログラミングコンテストチャレンジブック(2-3)の漸化式の説明が分からなかったのでググりをかましたら、わかりやすいのを見つけた。
プログラミングコンテストチャレンジブック特にGoで書く必要もなかったのでPythonでDP
n=4 m=3 M=10000 dp = [[0]*(n+1) for i in range(m+1)] dp[0][0] = 1 for i in range(1,m+1): for j in range(n+1): if j-i >= 0: dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M else: dp[i][j] = dp[i-1][j] print i,j,dp print dp[m][n]
dpを表示させてナニが起きてるのか確認。
1 0 [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 1 1 [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 1 2 [[1, 0, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 1 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 1 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 2 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 2 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]] 2 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 0, 0], [0, 0, 0, 0, 0]] 2 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 0], [0, 0, 0, 0, 0]] 2 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [0, 0, 0, 0, 0]] 3 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 0, 0, 0, 0]] 3 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 0, 0, 0]] 3 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 0, 0]] 3 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 0]] 3 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 4]] 4
O(n*m)の計算量ですな。