CSES — DP Coin Combination II TLE

→ Pay attention

Before contest
Educational Codeforces Round 172 (Rated for Div. 2)
15:06:11
Register now »

→ Streams

Codeforces Educational Round 172 — Solution Discussion

By Shayan

Before stream 17:11:10

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	orzdevinwang	3844
3	jqdai0815	3682
4	jiangly	3618
5	Benq	3529
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3443
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

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

View all →

→ Find user

→ Recent actions

Detailed →

Kaleab_Asfaw's blog

CSES — DP Coin Combination II TLE

By Kaleab_Asfaw, history, 4 years ago, In English

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 years ago
4

Comments (1)

Show archived | Write comment?

spookywooky

4 years ago, # |

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;
        }
    }

→ Reply