class Solution(object):
def checkPerfectNumber(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 1:
return False

s = 1
for i in xrange(2, int(num**(0.5))+1):
if num % i == 0:
s += i
if i != num/i:
s += num/i
return s == num


class Solution(object):
def complexNumberMultiply(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
def getri(s):
p = s.find('+')
r = int(s[:p])
i = int(s[p+1:-1])
return r, i

ra, ia = getri(a)
rb, ib = getri(b)
r = ra*rb - ia*ib
i = ra*ib + ia*rb

return '{}+{}i'.format(r, i)


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def boundaryOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []

p = root.left
left = []
while p:
left.append(p)
p = p.left if p.left else p.right
p = root.right

right = []
while p:
right.append(p)
p = p.right if p.right else p.left

def dfs(root, lst):
if not root:
return
if root.left or root.right:
dfs(root.left, lst)
dfs(root.right, lst)
else:
lst.append(root)
leaves = []
dfs(root, leaves)

ans = [root.val]
visited = set([root])
for p in left:
if p not in visited:
ans.append(p.val)

for p in leaves:
if p not in visited:
ans.append(p.val)

for p in reversed(right):
if p not in visited:
ans.append(p.val)

return ans


f(j, i) = max{f(k, i-1)+dp(k+1, j-1): k < j}

class Solution(object):
def removeBoxes(self, boxes):
"""
:type boxes: List[int]
:rtype: int
"""
memo = {}
def dp(l, r):
if l > r:
return 0
if l == r:
return 1
if (l, r) in memo:
return memo[l, r]

k = boxes[l]
lp = []
for i in xrange(l, r+1):
if k == boxes[i]:
lp.append(i)
n = len(lp)
if n == r-l+1:
memo[l, r] = ans = n * n
return ans

ans = 1 + dp(l+1, r)
tmp = [[0]*n for _ in xrange(n)]
for i in xrange(1, n):
for j in xrange(i, n):
for k in xrange(i-1, j):
if k+1 < j and lp[k]+1 == lp[k+1]:
continue
tmp[j][i] = max(tmp[j][i], tmp[k][i-1]+dp(lp[k]+1, lp[j]-1))
ans = max(ans, tmp[j][i]+(i+1)*(i+1)+dp(lp[j]+1,r))
memo[l, r] = ans
return ans

return dp(0, len(boxes)-1)