動的計画法

最近アルゴリズムの問題をを解けなかったが他人のコードを分析しようとしました。The problem involves a set of N cows numbered 0...(N-1). The objective is to determine the number of sets of K cows whose sum is a multiple of N. As this number may be more than the largest 32-bit integer, the problem is to find the number of sets mod 1000000007.
The number of sets of K cows is N choose K. However, determining which ones sum to cN is not immediately apparent.
The dynamic programming approach involves memoization in a two-dimensional array(二次元配列). The indices are the number of cows in the set to sum (j) and the remainder mod N (k). The problem then becomes how to find f[j][k] for j=K and k=0. There is clearly a dependency between f[j][k] and f[j-1][l] for all l. For example f[2][0] for N=10 includes sets {1,9},{2,8},{3,7},{4,6}. Thus, it would depend on f[1][1], f[1][2], f[1][3], f[1][4]. f[1][6] etc are redundant. How to encode this logic in a program is non-trivial, especially in one which can scale to all f[j][k].
The key insight is to see that, given that all sets involving cows 0-i are accounted for in the ith loop over the data structure, that all sets involving cows 0-(i+1) are accounted for in the (i+1)st loop. As none of the sets counted in the first i loops involve the (i+1)st cow, f[j][k] can be incremented by f[j-1][(k-i-1) or (k-i-1+N)]. k-i+N is used if k-i<0. i.e. 2nd index +(i+1) mod N is k. It can be proven that this holds for j=1 or 2. Then the general proof can be derived by induction. The algorithm runs in O(n^2m) where n is the total number of cows (N) and m is K.