< Back to forum

### 6 Answer(s)

0
Reply
Upvote

0
Reply
Upvote

##### Instruction to write good question

**Bad:** C# Math Confusion

**Good:** Why does using float instead of int give me different results when all of my inputs are integers?

**Bad:** [php] session doubt

**Good:** How can I redirect users to different pages based on session data in PHP?

**Bad:** android if else problems

**Good:** Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.

uestion : http://www.spoj.com/problems/COINS/

My solution : https://ideone.com/oMl9qP

Asked by: Shivam_Singhal on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

For a given value of n there can be only two possibilites :

1) n will give the maximum value .

2) exchange n into three coins : n/2, n/3 and n/4 and sum of these will give the maximum value.

these correspond to two states.

You can use :

a[n]=max(n,(max(n/2,fun(n/2))+max(n/3,fun(n/3))+max(n/4,fun(n/4))));

which basically reduces to:

a[n]=max(n,func(n/2)+func(n/3)+func(n/4));

you have used this: a[n]=max(n,(max(n/2,a[n/2])+max(n/3,a[n/3])+max(n/4,a[n/4]))); the func function is called only once in the main function and never in the function itself...therefore no recursion.. no memoization..no values stored in a (a will be empty). ans this expression will simply evaluate to - a[n]=max(n,(max(n/2,0)+max(n/3,0)+max(n/4,0))); so func will return with just one call.

- 1. Write a title that summarizes the specific problem
- 2. Pretend you're talking to a busy colleague
- 3. Spelling, grammar and punctuation are important!

Refer to Stack Overflow guide on asking a good question.