1
$\begingroup$

I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:

  • N = 5 + 2

  • N = 2 + 5

  • N = 2 + 2 + 3

  • N = 2 + 3 + 2

  • N = 3 + 2 + 2

But most of I found on the Internet that the different position is different way to express N (as this link for expressing N as sum of 1, 3, 4). Following that link, I try following DP formula:

    f[0] = f[1] = 0 ;
    f[2] = f[3] = f[4] = 1;
    for(int i = 5; i < 100; i++) {
        f[i] = f[i-2] + f[i-3] + f[i-5];
    }

But it isn't correct, as N = 7, F[N] = 4. So what is the correct DP method for this problem?

Hard version: I also concern about don't care order of way to express N, such as N = 2 + 2 + 3 and N = 2 + 3 + 2 and N = 3 + 2 + 2 will be only count as 1 time.

Note that I'm trying to solve above problem in complexity O(N).

$\endgroup$
  • $\begingroup$ I think your base cases are incorrect, f[0] and f[1] should also be 1. Alternatively, extend the base cases up to f[6]. Currently you would compute f[5] = f[3] + f[2] + f[0] = 2 which is clearly incorrect. $\endgroup$ – ryan Apr 25 at 3:26
  • $\begingroup$ @ryan Thank you and I've noticed that. So there is no way to express N = {0, 1} to sum of 2 3 and 5. So f[0] and f[1] should be 0, right? and how to deal with it? $\endgroup$ – Le Duong Tuan Anh Apr 25 at 3:34
  • $\begingroup$ Yeah that's true, leave f[0] and f[1] as is, that's why I said you could also extend the base cases up through f[6] to make things easier. $\endgroup$ – ryan Apr 25 at 3:47
  • 1
    $\begingroup$ The main issue is that you never introduce a way to use "5" in your base cases. Using f of 1 through 4 covers using "2" and "3" but not "5". You need to set f[5] = 3 basically. This also might be solved by setting f[0] = 1 because we can make 0 by using 0 counts of 2, 3, and 5. Then you get f[5] = 3 as expected. $\endgroup$ – ryan Apr 25 at 3:53
  • 1
    $\begingroup$ FWIW, linear DP is not the most efficient approach. For linear recursions like this you can set up a matrix power and calculate it in logarithmic time (assuming constant time arithmetic operations). $\endgroup$ – Peter Taylor Apr 25 at 6:57
2
$\begingroup$

It looks like you're missing some considerations with respect to the base cases. Since you're starting your for loop at i = 5, you should have base cases set for i = 0, 1, 2, 3, 4. f[0] = 1 since there's 1 way to choose a set of numbers that sums to 0 — choose nothing. f[1] = 0 since there's no way to make 1 out of 2, 3, and 5. f[2] and f[3] are both equal to 1 because they are in your set. Finally, f[4] = 1, since 2+2 = 4. This gives output f[7] = 5, as shown in your example cases.

For the "harder version", I suggest you look up the coin change problem. The problem formulation is essentially the same — how many ways are there to make up a given sum using a set of coins? The basic idea, and the one that prevents doubly counting permutations of the same solution, is that for each coin or value, you consider whether or not you wish to include it in the current solution set. If so, you get closer to the sum, and you can choose to reuse the same coin/value. If not, the value of your solution stays the same, but you never use that coin/value again in that solution. The final number of ways is just the sum of these two possibilities. Note that this method does have a time complexity of $O(mn)$.

Additional Links

https://www.geeksforgeeks.org/coin-change-dp-7/

$\endgroup$
  • $\begingroup$ Thank you so much for your fixes :D So how about for harder version? $\endgroup$ – Le Duong Tuan Anh Apr 25 at 4:02
  • $\begingroup$ Edited the answer. $\endgroup$ – jasli Apr 25 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.