kunal_rai's blog

By kunal_rai, history, 3 years ago, In English

The total number of elements in v can be up to N

const int N = 1e3;
int dp[N][N];
vector<vector<int>> v(N);

int go(int ind,int k) {
  if(ind == N)
    return 0;

  if(dp[ind][k] != -1)
    return dp[ind][k];

  int ans = go(ind + 1,k);

  for(int i: v[ind]) {
    if(k - i >= 0)
      ans = max(ans,go(ind + 1,k - i) + i);
  }

  return dp[ind][k] = ans;
}
  • Vote: I like it
  • -23
  • Vote: I do not like it

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

its O(N*N*K) I think.