TIMUS - 1036 Lucky Tickets

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).

UVA - 10839 - The Curse of Barbosa

problem statement
This problem is just a Dynamic Programming problem. Observe the problem as a graph with 3 nodes, if self loop was allowed in this problem then it would become a matrix multiplication problem, but now we have to count special paths, dp[x][y][z][node] means how many different roads can be made which city 1 is seen x times, city 2 is seen y times, city 3 is seen z times and we are at city 'node'. How to update this?

dp[x][y][z][node] += dp[x-1][y][z][1]  if node != 1
dp[x][y][z][node] += dp[x][y-1][z][2]  if node != 2
dp[x][y][z][node] += dp[x][y][z-2][3]  if node != 3

We know the basic case dp[0][0][0][1] = 1, in this way we can update our table.
Each time we read n, output = dp[n/3][n/3][n/3][1] is the number of ways we can start from 1 and end at 1, but output counts some paths and it's reverse, some paths not all paths, palindrome paths are counted just once, their reverse is not counted, so if we add the number of palindrome paths, we can divide that number by two.
How to add palindrome paths? If n is even then there is no palindrome path, but if n is odd,  m = (n+1)/2, and we calculate dp[m/3][m/3][m/3][1] and add it to dp[n/3][n/3][n/3][1], the result would be (dp[m/3][m/3][m/3][1] + dp[n/3][n/3][n/3][1] ) / 2. (Of course we need BigInteger here.)