My first DP problem

[1vf9z8AR]

Hi. I solved my first dynamic problem but my answer is coming as wrong on online judge. For the test cases, the output is correct.

Question link-
https://www.spoj.com/problems/COINS/

My attempt-

    #include<iostream>
using namespace std;
long int sumlist[100000];
long int memo(long int no)
{
    if(no>=100000)
        return memo(no/2)+memo(no/3)+memo(no/3);
    if(sumlist[no]!=0 || no==0)
        return sumlist[no];
    else
    {
        long int sum=memo(no/2)+memo(no/3)+memo(no/4);
        if(sum>no)
            sumlist[no]=sum;
        else
            sumlist[no]=no;
    }
    return sumlist[no];
}
int main()
{
    sumlist[0]=0;
    sumlist[1]=1;
    sumlist[2]=2;
    for(long int i=3;i<100000;i++)
        sumlist[i]=0;
    long int no;
    while(cin>>no)
    {
        long int ans=memo(no);
        cout<<ans<<endl;
    }
    return 0;
}

[tpb]

Read line 7 very carefully.

[tpb]

It passes the two test cases that they give, but what about your own test cases? Even after fixing line 7 I still don't think it's giving the right answer.

An input of 5 should return 4 (your code says 5).

5: 5/2 + 5/3 + 5/4 = 2 + 1 + 1 = 4
4: 4/2 + 4/3 + 4/4 = 2 + 1 + 1 = 4

An input of 20 should return 23 (your code says 21).

  20/2 + 20/3 + 20/4 = 10 + 6 + 5 = 21
  21/2 + 21/3 + 21/4 = 10 + 7 + 5 = 22
  22/2 + 22/3 + 22/4 = 11 + 7 + 5 = 23
  23/2 + 23/3 + 23/4 = 11 + 7 + 5 = 23

I think there is a fundamental flaw in your algorithm.
Your code relies on, e.g.,

    m(20) = m(10) + m(6) + m(5)

But that isn't true since that's just

            10    + 6    + 4     = 20  (where it will stay; should become 23)

[Browni3141]

I recommend using std::unordered_map for your lookup table.
http://www.cplusplus.com/reference/unordered_map/unordered_map/

tpb wrote:

I think there is a fundamental flaw in your algorithm.
Your code relies on, e.g., m(20) = m(10) + m(6) + m(5)

This isn't quite true. For sufficiently large N, N < m(N/2)+m(N/3)+m(N/4). 100,000 is definitely large enough, but OP should be careful coding like this. When OP corrects line 7 I think he probably gets the right answer. I think you misunderstood the problem as your algorithm isn't correct.

An input of 5 should return 4 (your code says 5).

An input of N should never return less than N.

An input of 20 should return 23 (your code says 21).

An input of 20 returns 21. You used the wrong algorithm:
20/2+20/3+20/4 = 10+6+5 = 21 (improvement, trade for 3 more coins)

10/2+10/3+10/4 = 5+3+2 = 10 (no improvement, exchange for $)
6/2+6/3+6/4 = 3+2+1 = 6 (no improvement, exchange for $)
5/2+5/3+5/4 = 2+1+1 = 4 (no improvement exchange for $)

Edit: I signed up for online judge and submitted my own solution to the problem which worked. My program works up to inputs of about 10^17.

[tpb]

You're right. I wasn't paying attention. I was adding the total value of the 3 new coins together and treating them as one coin again. Since they are separate coins, the algorithm can obviously be done the way he's done it.