Why the Time Complexity of this function is O(N * N)?

Правка en1, от kunal_rai, 2021-07-28 15:44:52

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;
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский kunal_rai 2021-07-28 15:44:52 450 Initial revision (published)