Count the number of ways in which a number 'A' can be broken into a sum of 'B' numbers such that all numbers are co-prime to 'C'
- by rajneesh2k10
I came across the solution of a problem which involve dynamic-programming approach, solved using a three dimensional matrix.
Link to actual problem is: http://community.topcoder.com/stat?c=problem_statement&pm=12189&rd=15177
Solution to this problem is here under MuddyRoad2: http://apps.topcoder.com/wiki/display/tc/SRM+555
In the last paragraph of explanation, author describes a dynamic programming approach to count the number of ways in which a number 'A' can be broken into a sum of 'B' numbers (not necessarily different), such that every number is co-prime to 3 and the order in which these numbers appear does matter.
I am not able to grasp that approach. Can anyone help me understand how DP is acting here. I can't understand what is a state here and how it is derived from the previous state.