Every big thing has a small beginning


  • 2

    I have to say, reading this problem and several explanation posts/discussion really inspire me a lot.

    After first time reading this problem, i am overwhelmed by so many cases/ possibilities. Well, typically this indicates dynamic programming.

    It is so complicate because I am looking into a wrong way.

    say have A = [1, 2, 10, 20] n=100

    Things come to my mind is, how many kinds of different sums could A provide? by adding a number how those sums to expand? how to choose this one number to add?

    How about this.
    say have A=[1] n = 100 . how do we patch ?

    well, everybody knows need to patch 2 fist, of course there is no other choice.

    then, it is not hard to realize we need to add 4 then, because [1,2] result in 1,2,3 and stopped at 3.

    Of course we would choose 4 as next, compared 1,2,3 ( adding 1 give us all sum as : 1,2,3,4 however adding 4 give us all sum as : 1,2,3,4,5,6,7)

    I believe now everybody knows how to tackle this problem. Same thing repeat till 100 is reached.

    let's look back at A = [1,2,10,20]

    by having 1 ,2, we have all possible sum as : 1,2,3

    then we have 10

    (10 itself gives a sum as 10, and having 10 of course all sums from 10 to 13)

    but we missing 4 - 10 here, and the one we miss immediately is 4

    It is the same thing as we only have [1,2], we also miss 4. what we do is adding 4

    same here, we add 4, and now we have all sum as : 1, 2, 3, 4, 5, 6, 7

    So u can tell now, though we having a number 10 sitting there, but what we doing is exactly the same as we not having it. just patch the immediate missing one.

    U can just consider 10 the same as we patch it when it is the immediate missing. after a patching, it expand our all sum.

    So the question, why having A = [1] instead of A = [1,2, 10, 20] make this problem much easier?
    Because A = [1] kindly remove the confusing and unnecessary complicity for us.

    Now let's look back those complicity, the reason it is so complicated is because we are not seeing the pattern but seeing the whole issue at one time instead.

    The pattern is the subproblem and the connection between subproblems.

    In this case a subproblem is when we have A = [...] which could give us all sum from 1 to k.
    how to we patch to expand it most efficiently ? we know now by adding k+1

    Yes, and that is the connection. now subproblem turns into A = [...., k+1] give us all sum from
    1 to k+k+1 , how to expand it most efficiently?

    Each question could be very unique, but as long as it is a dp/greedy problem. Everybody knows, find the subproblem and find the transfer between subproblems.

    But how to discover the subproblem is really challenging always.

    Till now, I would say, first is never be deceived by the complicity.
    second, analyze what is the final goal of the question.
    third, how does this problem initiate, what is the first stage.
    forth, again, understand in context what is A step
    finally, figure out the restrictions/requirement to transfer between steps

    This is just for my own information and for yours if needed the same.


  • 0
    C

    nicely explained!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.