Loop related concept query

#1

what is difference between the following two loops,which to use when (different places interchangebly use in coin change problem)

  1. for(int i=0;i<n;i++)
    {
    for(int j=1;j<=target;j++)
    {
    }
    }
  1. for(int i=1;i<=target;i++)
    {
    for(int j=0;j<n;j++)
    {
    }
    }
    where n is number of elements in array
#2

hello @spagire4
both will store same information just indexing will change.

for example the information stored at index (i,j) in first approach will be equal to the information store at index (j,i) in second.

#3

@aman212yadav why both give write answer
for(int i=1;i<coins.length;i++)
{
for(int j=1;j<=amount;j++)
{
if(j>=coins[i])
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
else
dp[i][j]=dp[i-1][j];
}
}

///////2nd one
for(int j=1;j<=amount;j++)
{
for(int i=1;i<coins.length;i++)
{
if(j>=coins[i])
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
else
dp[i][j]=dp[i-1][j];
}
}

return dp[coins.length-1][amount];

}
}
}

#4

in first approach
dp[i][j] = stores answer for first i coins and total amount j .

so dp[coins.lenght-1][amount] will store answer when all coins are considered and complete given amount is considered.

in second approach
dp[j][i] = stores answer for first i coins and total amount j .

so dp[amount][coins.lenght-1] will store answer when all coins are considered and complete given amount is considered.

both the approach are telling u same answer at the end.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.