UVA 1213 — Sum of Different Primes, Help !!

→ Pay attention

Before contest
EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
25:02:48
Register now »

*has extra registration

→ Streams

Atcoder ABC #360 Solution Discussion

By aryanc403

Before stream 24:12:47

View all →

→ Top rated

#	User	Rating
1	tourist	3845
2	jiangly	3707
3	Benq	3630
4	orzdevinwang	3573
5	Geothermal	3569
5	cnnfls_csy	3569
7	jqdai0815	3532
8	ecnerwala	3501
9	gyh20	3447
10	Rebelz	3409

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	171
2	awoo	163
3	adamant	162
4	maroonrk	152
5	nor	151
5	-is-this-fft-	151
7	atcoder_official	147
7	TheScrasse	147
9	Petr	145
10	pajenegod	144

View all →

→ Find user

→ Recent actions

Detailed →

UVA 1213 — Sum of Different Primes, Help !!

Revision en2, by approach, 2021-10-01 11:34:00

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

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en2		approach	2021-10-01 11:34:00	7
	en1		approach	2021-10-01 11:22:35	1190	Initial revision (published)