CSES — DP Coin Combination II TLE

Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

До соревнования
Codeforces Round (Div. 2)
3 дня
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

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

Всё →

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

№	Пользователь	Вклад
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя Kaleab_Asfaw

CSES — DP Coin Combination II TLE

Автор Kaleab_Asfaw, история, 4 года назад, По-английски

Getting TLE with a python solution for Coin Combination problem in here

I know that python is slow ..., but have seen other python users solving it here

My Code

def solve(n, x, lst):
    dp = []
    for i in range(n+1):
        temp = [1] + [0]*x
        dp.append(temp)

    for i in range(1, n+1):
        for j in range(1, x+1):
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
            if j - lst[i-1] >= 0:
                dp[i][j] = (dp[i][j] + dp[i][j - lst[i-1]]) % mod
    for i in dp: print(i)
    return dp[n][x]

n, x = list(map(int, input().split()))
lst = list(map(int, input().split()))
print(solve(n, x, lst))

...

Creating the dp 2D array is even taking much time. Is there a way it can be optimized?

Thanks for taking your time and reading this!

dp, #dynamic programing, #tle, #optimization

Kaleab_Asfaw
4 года назад
4

Комментарии (1)

Показать архивные | Написать комментарий?

spookywooky

4 года назад, # |

The dp can be 1 dimensional, let c[] be the coins and x the sum, then dp[x] is the answer:

    dp[0]=1;
    for(int a : c) {
        for(int i=0; i+a<=x; i++) {
            dp[i+a]+=dp[i];
            dp[i+a]%=MOD;
        }
    }

→ Ответить

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

Время на сервере: 02.10.2024 23:39:59 (j2).

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

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