UVA 1213 — Sum of Different Primes, Help !!

→ Обратите внимание

До соревнования
Codeforces Round (Div. 2)
6 дней

→ Трансляции

CodeChef Starters 141 Solution Discussion

aryanc403

До начала 47:48:32

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3803
2	jiangly	3707
3	Benq	3627
4	ecnerwala	3584
5	orzdevinwang	3573
6	Geothermal	3569
6	cnnfls_csy	3569
8	Radewoosh	3542
9	jqdai0815	3532
10	gyh20	3447

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	167
2	awoo	164
3	adamant	162
4	maroonrk	152
5	-is-this-fft-	151
5	nor	151
7	atcoder_official	147
8	TheScrasse	146
9	Petr	145
10	pajenegod	143

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

UVA 1213 — Sum of Different Primes, Help !!

Правка en2, от 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

История

Правки

	Rev.	Язык	Кто	Когда	Δ	Комментарий
	en2		approach	2021-10-01 11:34:00	7
	en1		approach	2021-10-01 11:22:35	1190	Initial revision (published)

Соревнования по программированию 2.0

Время на сервере: 01.07.2024 20:11:28 (i1).

Десктопная версия, переключиться на мобильную.

При поддержке