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.
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.