Andy
BAN USERA solution that saves state.
public class NumberProblem
{
// for length two, we know the answer.
private int[][] lengthTwoResults =
{{ 4,5,6,7,8,9 },
{ 5,6,7,8,9},
{ 6,7,8,9 },
{ 7,8,9 },
{ 0,8,9 },
{ 0,1,9 },
{ 0,1,2 },
{ 0,1,2,3 },
{ 0,1,2,3,4 },
{ 0,1,2,3,4,5 }
};
private int[][] countState; // Store state.
public void main(String args[])
{
int count = 0;
int n = 5;
countState = new int[n-1][];
for (int i = 0; i < n-1; i++)
{
// Set up matrix
countState[i] = new int[10];
}
// Loop through possible start numbers (1-9). So number starting with 0 not allowed.
for (int i = 1; i < 9; i++)
{
count += getCount(i, n-1);
}
System.out.println("Count is " + count);
}
/**
* Recursively go through possible numbers after a prefix.
**/
public int getCount(int prefixNumber, int n)
{
/* Bottom layer of recursion. We’ve got one more number to go.
* Check the above array. */
if (n == 1)
{
return lengthTwoResults[prefixNumber].length;
}
// Check to see if we’ve calculated this result before.
if (countState[n-1][prefixNumber] != 0)
{
// If so, return it.
return countState[n-1][prefixNumber];
}
int count = 0;
// Else, loop through all of the possible next-numbers.
for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
{
// Have we calculated those results before?
if (countState[n-2][nextPossibleNumber] != 0)
{
// Yes, just add to count.
count += countState[n-2][nextPossibleNumber];
} else {
int subCount = getCount(nextPossibleNumber, n-1);
// Save result in matrix for next time.
countState[n-2][nextPossibleNumber] = subCount;
count += subCount;
}
}
// Save result of this value of n and prefix for next time.
countState[n-1][prefixNumber] = count;
return count;
}
}
Use the fact that addition is commutative to solve this. You don't need to try a number again if you used it higher up the recursion layer, and found it didn't work. But you do for each different prefix set of numbers.
- Andy August 02, 2015