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;
}
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].
I am sorry but can you explain further your answer ?
The transitions should be something like this:
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.
thank you so much i've made change in your comment and now accepted ^_^