UVA 1213 — Sum of Different Primes, Help !!

approach's blog

By approach, history, 5 years ago, In English

Problem Link so, I was able to come up with memoization approach, but unable to write iterative version.

The correct one happens to be

Correct implementation

vector<vector<int>> dp(16, vector<int>(1180, 0));
  
  dp[0][0] = 1;

  for (int i = 0; i < arePrimes.size(); i++)
    for (int k = 14; k >= 1; k--)
      for (int n = 1170; n >= arePrimes[i]; n--)
        dp[k][n] += dp[k - 1][n - arePrimes[i]];
  
  cout << dp[K][N] << '\n';

But I failed to realise, why this one is wrong.

wrong one

    vector<vector<int>> dp(16, vector<int>(1180, 0));

    dp[0][0] = 1;

    for (int i = 0; i < arePrimes.size(); i++)
      for (int k = 1; k <= 14; k++)
        for (int n = arePrimes[i]; n <= 1170; n++)
          dp[k][n] += dp[k - 1][n - arePrimes[i]];

    cout << dp[K][N] << '\n';

could u help me out please, any kind of help on how to approach such iterative DP problems, will be appreciated.