Clarification on the problem description. [Problem description need to be updated !!! ]


  • 50

    It is actually confusing that the example shown in the problem description is not the best stragety to guess the final target number, and the problem itself is asking for the lowest cost achieved by best guessing strategy.
    The example description should be updated.

    ---POSSIBLY, it can also add some example about the BEST Strategy---
    The example description should be:

    first introducebest strategyto guess:

    1. for one number, like 1, best strategy is 0$
    2. for two number, like 3,4, best strategy is 3$, which can be understood in this way: you have two way to guess: a) start by guess 4 is the target, (the worst case is) if wrong, you get charged $4, then immediately you know 3 is the target number, get get charged $0 by guessing that, and finally you get charged $4. b) similarly, if you start by 3, (the worst case is) if wrong, you get charged $3, then you immediately know that 4 is the target number, and get charged $0 for guessing this, and finally you get charged $3. In summary:
      range ---------> best strategy cost
      3, 4 ---------> $3
      5, 6 ---------> $5
      ...
    3. for three number, the best strategy is guess the middle number first, and (worst case is) if wrong, you get charged that middle number money, and then you immediately know what target number is by using "lower" or "higher" response, so in summary:
      range ---------> best strategy cost
      3, 4, 5 ---------> $4
      7, 8, 9 ---------> $8
      ...
    4. for more numbers, it can simply be reduced them into smaller ranges, and here is why DP solution make more sense in solving this.
      suppose the range is [start, end]
      the strategy here is to iterate through all number possible and select it as the starting point, say for any k between start and end, the worst cost for this is: k+DP( start, k-1 ) + DP(k+1, end ), and the goal is minimize the cost, so you need the minimum one among all those k between start and end

  • 0
    L

    Feeling much better after reading your post, thanks for sharing your thoughts!


  • 0

    No problem. Yeath, I was also very confused at beginning, I am glad i can help !


  • 0
    A

    This clarification and examples are very helpful!


  • 0

    @AlexSong i am glad it helps


  • 0
    Y

    Could't understand the question before reading your post.
    Feelsgoodman, Thanks


  • 0

    @yrq glad it helps, cheers


  • 5
    J

    Hi, thanks for your explanation, for more numbers case, say for any k between start and end, the worst cost for this is: k+ max(DP( start, k-1 ), DP(k+1, end )) instead of k+DP( start, k-1 ) + DP(k+1, end ). Since we don't know whether high or low, just pick worst case. Correct me if I'm wrong.


  • 1
    T

    for four numbers, the best strategy is the first number + the third number
    for five numbers, the best strategy is the second number + the fourth number


  • 0
    Z

    @realdonaldtrump I dont know Donald Trump can code, lol...


  • 0
    M

    thanks mate, it helps a lot


  • 0
    A

    thank you so much for sharing your idea!!!
    i got totally confused by the description of this problem.


  • 0

    @jianoffer Good catch. Made the same mistake with the president


Log in to reply
 

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