Link to the problem on Timus Online Judge
First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or second if sum/2 > n*9, in first case we can not divide sum in two parts equally, in second case if we put 9 in all positions we can not make sum/2.
This is a Dynamic Programming problem, state of our dp is : dp[i][sum] which means we are on digit i and we want to make sum, how do we do that? We have to find sub-problems related to this state.
dp[i][sum] = SUM{ dp[i-1][sum-k] for k = 0...9, st sum-k >= 0 }
The base case is that we know dp[0][0] = 1, which means there is one way to make sum of zero with zero digits, and that is nothing! :) ( like combination(0, n) = 1 )
And what is the answer after calculating dp[i][sum]?
The answer is dp[n][sum/2]*dp[n][sum/2] (multiplication principle).
First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or second if sum/2 > n*9, in first case we can not divide sum in two parts equally, in second case if we put 9 in all positions we can not make sum/2.
This is a Dynamic Programming problem, state of our dp is : dp[i][sum] which means we are on digit i and we want to make sum, how do we do that? We have to find sub-problems related to this state.
dp[i][sum] = SUM{ dp[i-1][sum-k] for k = 0...9, st sum-k >= 0 }
The base case is that we know dp[0][0] = 1, which means there is one way to make sum of zero with zero digits, and that is nothing! :) ( like combination(0, n) = 1 )
And what is the answer after calculating dp[i][sum]?
The answer is dp[n][sum/2]*dp[n][sum/2] (multiplication principle).
No comments:
Post a Comment