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.)
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.)
No comments:
Post a Comment