### FameOfTheLegends's blog

By FameOfTheLegends, 2 months ago,

I was doing this Problem on codeforces. It was a dynamic programming question and I am fairly new to dynamic programming.

I wrote a code whose main part is below

n,m,b,mod = li()
a = li()
dp = [[0 for i in range(b+1)] for j in range(m+1)]
dp[0][0]=1
for i in range(n):
for j in range(1,m+1):
for k in range(b+1):
if k-a[i]>=0:
dp[j][k]+=dp[j-1][k-a[i]]
ans = 0
for j in range(b+1):
ans+= dp[m][j]
print(ans%mod)


This was giving the correct output. But when I move the first loop to the end, then it gives the wrong answer.

for j in range(1,m+1):
for k in range(b+1):
for i in range(n):
if k-a[i]>=0:
dp[j][k]+=dp[j-1][k-a[i]]


The above code is giving incorrect output. Can anybody help me in understanding why does the loop orientation matters in this case.

• +1

 » 2 months ago, # | ← Rev. 2 →   +44 In the problem statement author write that $i-th$ programmer write $V_i$ lines consecutive and he write code earlier than $(i + 1)-th$ programmer, but in the second solution programmer don't write lines of code consecutive, and $(i + 1)-th$ coder can write code earlier than $i-th$ coder.For example test:$2$ $3$ $0$ $10000000$$0$ $0$Solution number 1 print 4: "1 1 2", "1 2 2", "1 1 1", "2 2 2".Solution number 2 print 8: "1 1 2", "1 2 2", "1 1 1", "2 2 2", "2 1 1", "2 2 1", "1 2 1", "2 1 2".We can observate that second solution count incorrect answers.