1213 — Sum of Different Primes, Help !!

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
17:53:05
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 19:23:03

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 20:53:03

Всё →

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

№	Пользователь	Рейтинг
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

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

Всё →

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

№	Пользователь	Вклад
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

Всё →

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

→ Прямой эфир

Детальнее →

1213 — Sum of Different Primes, Help !!

Правка en1, от approach, 2021-10-01 11:22:35

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

Время на сервере: 22.11.2024 23:41:57 (h1).

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

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