FilesExpand file tree

 master

/

BurstBalloons.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (44 loc) · 1.79 KB

 master

/

BurstBalloons.py

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (44 loc) · 1.79 KB

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

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

'''Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.

(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []

coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

'''

class Solution(object):

def maxCoins(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

res = 0

nums.append(res)

sols = [nums]

i = 0

while True:

todo = sols[i]

if len(todo) == 1:

res = todo[-1]

for x in range(i, len(sols)):

if res < sols[x][-1]:

res = sols[x][-1]

return res

for x in range(len(todo) - 1):

if x == 0:

print('--------')

print(sols)

if len(todo) == 2:

res = todo[0] + todo[-1]

elif x == 0:

res = todo[x] * todo[x + 1] + todo[-1]

elif x == len(todo) - 2:

res = todo[x] * todo[x - 1] + todo[-1]

else:

res = todo[x] * todo[x - 1] * todo[x + 1] + todo[-1]

sols.append(todo[:x] + todo[x + 1:-1] + [res])

i += 1

print(Solution().maxCoins([3, 1, 5, 8]))