FilesExpand file tree

master

/

Guess_Number_Higher_or_Lower_II.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

20 lines (14 loc) · 403 Bytes

master

/

Guess_Number_Higher_or_Lower_II.py

Copy path

Top

File metadata and controls

• Code
• Blame

20 lines (14 loc) · 403 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# -*- coding:utf-8 -*-

import sys

class Solution(object):

def getMoneyAmount(self, n):

dp = [[0] * (n+1) for _ in range(n+ 1)]

for gap in range(1, n):

for low in range(1, n + 1 - gap):

high = low + gap

dp[low][high] = min(x + max(dp[low][x-1], dp[x+1][high])for x in range(low, high))

return dp[1][n]

if __name__ == "__main__":

s = Solution()

n = 10

print s.getMoneyAmount(n)