another dp

TheSwap

framework for a dp solution

// memoization unit
int memo[][];

int main() {

  // reset memo
  memset(memo, 0, sizeof(memo));

  // calling subroutine to iteratively solve the problem
  return doit();
}


int doit(int n, int k ) {
  //if already visited state, return memo[][];
  if (memo[][] != 0) return memo[][];

  // if it is the stopping condition, return memo[] = ? //
  // e.g., k = 0 return n????

  // initialize return value
  int ret = 0; // -1 sometimes

  for(all the possible variables) {
    for(for the possible variables) {

      // pre-processing to get n_1

      // enter subproblem
      // comparison_funct, e.g., max, min, ++
      // note k-1 below, this identifies the subproblem
      ret = comparison_function(ret, doit(n_1, k-1) ) ; 

      // post-processing to get back n
      // we might need some processing to retrieve n in the original problem 
      n = f(n_1);
    }
  }

  // this state is visited, set it in the memo
  return ret = memo[][];

}

int doit(vector &v, int k) {
  int rv = get_v(v);

  // visited
  if(memo[rv][k] != 0) return memo[rv][k];

  if(k == 0) return memo[rv][k] = rv;

  int a = -1;
  for(int i = 0; i < v.size(); ++i) {
    for(int j = i+1; j < v.size(); ++j) {

      // excluded cases: highest digit does not swap with '0'
      if (j == v.size()-1 && v[i] == 0) continue;

      // pre-processing
      int tmp = v[i];
      v[i] = v[j], v[j] = tmp;
      // enter subproblem
      a = max(a, doit(v, k-1));

      // post-processing
      v[j] = v[i], v[i] = tmp;
    }
  }
      
  return memo[rv][k] = a;
}

For another problem in NumbersAndMaches.

const int dis[10][7] =
{
  {1, 1, 1, 0, 1, 1, 1},
  {0, 0, 1, 0, 0, 1, 1},
  {1, 0, 1, 1, 1, 0, 1},
  {1, 0, 1, 1, 0, 1, 1},
  {0, 1, 1, 1, 0, 1, 0},
  {1, 1, 0, 1, 0, 1, 1},
  {1, 1, 0, 1, 1, 1, 1},
  {1, 0, 1, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1},
  {1, 1, 1, 1, 0, 1, 1},
};


long long dp[20][127][127];

int _inc[10][10], _dec[10][10];

int k;
long long solve(long long N, int idx, int added, int removed) {
 
  if (dp[idx][added][removed] != -1) 
    return dp[idx][added][removed];

  if(N == 0) {
    if (added == removed && added <= k) {
      return 1LL;
    }
    return 0LL;
  }

  int i = N % 10;
  long long ret = 0;
  for(int j = 0; j <= 9; ++j) {
    ret += solve(N/10, idx+1, added + _inc[i][j], removed + _dec[i][j]);
  }
  return dp[idx][added][removed] = ret;
}
  
long long NumbersAndMatches::differentNumbers(long long N, int K)
{
    for (int i = 0; i < 10; i ++)
      for (int j = 0; j < 10; j ++)
      {
        _inc[i][j] = _dec[i][j] = 0;
        for (int k = 0; k < 7; k ++)
        {
          if (dis[i][k] < dis[j][k])
            _inc[i][j] ++;
          if (dis[i][k] > dis[j][k])
            _dec[i][j] ++;
        }
      }
    k = K;
    memset(dp, -1, sizeof(dp));
    return solve(N, 0, 0, 0);    
}