Tensor's blog

help in dp problem ?
By Tensor, 10 years ago, In English

I have been solving this problem, but i don't know what is wrong with my submission.

#include <unordered_map>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <unordered_set>

using namespace std;

const int N = 101, inf = 1e9;

char a[N], b[N];

int f[N][N][N], n, m;

int dp(int i, int j, int k, int val) {
  if (i < 0 || j < 0)
    return -inf;
  if (k == 0)
    return val;
  int &ret = f[i][j][k];
  if (ret + 1)
    return ret;
  ret = 0;
  if (a[i] == b[j])
    ret = max(ret, dp(i - 1, j - 1, k - 1, val + a[i]));
  else {
    ret = max(ret, dp(i - 1, j, k, val));
    ret = max(ret, dp(i, j - 1, k, val));
  }
  return ret;
}

int main(void) {
#ifdef DEBUG  
  freopen("in.txt", "r", stdin);
//  freopen("o.txt", 'w', stdout);
#endif
  int tc, k;
  for (scanf("%d", &tc); tc--; ) {
    scanf("%s %s %d", a, b, &k);
    n = (int)strlen(a), m = (int)strlen(b);
    memset(f, -1, sizeof(f));
    printf("%d\n", dp(n - 1, m - 1, k, 0));
  }
  return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you have a[i] = b[j] in your recursion it doesn't mean that you should necessarily pick these characters to create the subsequence and transition to k-1. You could also create a subsequence of length K of maximal value from a[1..i - 1] and b[1..j], or a[1..i] and b[1..j - 1].

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am sorry but can you explain further your answer ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 5   Vote: I like it +3 Vote: I do not like it

      The transitions should be something like this:

      if (a[i]==b[j]) ret = max(ret, a[i]+dp(i - 1, j - 1, k - 1));
ret = max(ret, dp(i - 1, j, k));
ret = max(ret, dp(i, j - 1, k));

      Also if you reach i = 0 or j = 0 and you have k > 0 you should return "minus infinity"(something like -2^30). Also the fourth parameter that you used is kinda useless, just return 0 when you reach K=0.

      Here's my solution that passed if you still have problems understanding: http://ideone.com/tI8d2a I use a big negative constant to ignore impossible solutions.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thank you so much i've made change in your comment and now accepted ^_^

        → Reply