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 '19 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 '19 at 3:34
  • 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 '19 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 '19 at 6:57
  • 1
    $\begingroup$ @PeterTaylor that's also a very good point. Think you could write it up as an answer? It's another really good alternative. $\endgroup$ – ryan Apr 25 '19 at 16:52
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/

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you so much for your fixes :D So how about for harder version? $\endgroup$ – Le Duong Tuan Anh Apr 25 '19 at 4:02
  • $\begingroup$ Edited the answer. $\endgroup$ – jasli Apr 25 '19 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.