UVA 1213 — Sum of Different Primes, Help !!

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:32:05
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

approach's blog

UVA 1213 — Sum of Different Primes, Help !!

By approach, history, 3 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.

need help, uva, dp problem, iterative dp

approach
3 years ago
1

Comments (0)

Show archived | Write comment?