why n=6 get 8 instead of 9?


  • 2
    Z

    should it be 3+5+1?


  • 3
    Z

    Hi Zerghua, if you choose 3 first, then the possible number maybe in [1,2] or [4,6]. If it's in [1,2] interval, the minimum cost will be 3+1=4. If it's in [4,6], the minimum cost is 3+5=8. Here since 8 is greater then 4, we can promise 8 is sufficient.
    To be short, if you suggest choosing 3 first, the formula should be 3+max(min[1,2],min[4,6]) instead of min[1,2]+3+min[4,6].


  • 0
    Z

    @zpcore Thanks for your explanation, that makes sense.


Log in to reply
 

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