Dynamic programming algorithm

Question

Hi I have a question on an existing algo problem.

Existing problem description: Generate 10-digit number using a phone keypad

1 2 3
4 5 6
7 8 9
  0

Answer 1

Though this question has a tag of C++, consider this pseudo-code to express the algorithm (which conveniently happens to be written in ruby.)

# Where the knight can jump to
$m = {
  0 => [4,6], 1 => [6,8], 2 => [7,9], 3 => [4,8], 4 => [0,3,9],
  5 => [], 6 => [0,1,7], 7 => [2,6], 8 => [1,3], 9 => [2,4]
}

$cache = Hash.new
# return count
def nseq( k, n, e=0 )
  e += 1 if k.even?
  return 0 if 3 < e
  return 1 if n == 1
  key = "#{k}:#{n}:#{e}" # for the memoization
  return $cache[key] if $cache.has_key? key
  # Sum nseq(j,n-1,e) for j in $m[k]
  return $cache[key] = $m[k].inject(0) { |sum,j| sum + nseq( j, n-1, e ) }
end

0.upto(9) do |k|
  2.upto(8) do |n|
    count = nseq(k,n)
    puts "k=#{k},n=#{n}: #{count}"
    break if count.zero?
  end
end

This outputs

k=0,n=2: 2
k=0,n=3: 6
k=0,n=4: 8
k=0,n=5: 16
k=0,n=6: 0
k=1,n=2: 2
k=1,n=3: 5
k=1,n=4: 10
k=1,n=5: 24
k=1,n=6: 32
k=1,n=7: 64
k=1,n=8: 0
k=2,n=2: 2
k=2,n=3: 4
k=2,n=4: 10
k=2,n=5: 16
k=2,n=6: 32
k=2,n=7: 0
k=3,n=2: 2
k=3,n=3: 5
k=3,n=4: 10
k=3,n=5: 24
k=3,n=6: 32
k=3,n=7: 64
k=3,n=8: 0
k=4,n=2: 3
k=4,n=3: 6
k=4,n=4: 14
k=4,n=5: 16
k=4,n=6: 32
k=4,n=7: 0
k=5,n=2: 0
k=6,n=2: 3
k=6,n=3: 6
k=6,n=4: 14
k=6,n=5: 16
k=6,n=6: 32
k=6,n=7: 0
k=7,n=2: 2
k=7,n=3: 5
k=7,n=4: 10
k=7,n=5: 24
k=7,n=6: 32
k=7,n=7: 64
k=7,n=8: 0
k=8,n=2: 2
k=8,n=3: 4
k=8,n=4: 10
k=8,n=5: 16
k=8,n=6: 32
k=8,n=7: 0
k=9,n=2: 2
k=9,n=3: 5
k=9,n=4: 10
k=9,n=5: 24
k=9,n=6: 32
k=9,n=7: 64
k=9,n=8: 0

The result is the number of all n-length sequences starting on key k, which have no more than 3 even digits in them. For example, the last entry is k=9,n=8: 0. This means that all sequences of length 8 starting on key 9 include more than 3 even digits.

EDIT: Here it is translated into C++. It produces identical output as above.

#include<iostream>
#include<map>
using namespace std;

const int MAX_EVENS = 3; // Assume < 8

// Where the knight can jump to
const int jumpto[][3] = { {4,6}, // 0
  {6,8}, {7,9}, {4,8},   // 1 2 3
  {0,3,9}, {}, {0,1,7},  // 4 5 6
  {2,6}, {1,3}, {2,4} }; // 7 8 9
const int jumpto_size[] = { 2, // 0
  2, 2, 2,   // 1 2 3
  3, 0, 3,   // 4 5 6
  2, 2, 2 }; // 7 8 9

typedef map<unsigned,int> cachetype;
cachetype cache;

int nseq( int k, int n, int e=0 )
{
  e += k&1^1; // increment e if k is even.
  if( MAX_EVENS < e ) return 0;
  if( n <= 1 ) return 1;
  unsigned key = (n << 4 | k) << 3 | e; // n is left with 32-7=25 bits
  cachetype::const_iterator it = cache.find(key);
  if( it != cache.end() ) return it->second;
  int sum = 0;
  for( int i=0 ; i<jumpto_size[k] ; ++i ) sum += nseq( jumpto[k][i], n-1, e );
  return cache[key] = sum;
}

int main()
{
  for( int k=0 ; k<=9 ; ++k )
    for( int n=2 ; n<=8 ; ++n )
    {
      int count = nseq(k,n);
      cout << "k="<<k<<",n="<<n<<": "<<count<<endl;
      if( count == 0 ) break;
    }
  return 0;
}