目录
- 53、max subarray
- 62、unique paths
- 63、unique path2
- 70、climbing stairs
- 91、decode ways
- 120、triangle
- 121、best time sell and buy stocks
- 139、 Word Break
- 152、Maximum Product Subarray
- 198、 House Robber
- 213、house robber II
- 221、 Maximal Square
- 264、Ugly Number II （比较重要）
- 279、Perfect Squares
- 300、Longest Increasing Subsequence （比较重要）
53、max subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
my answer:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is []:
return 0
max_dict = {}
for i, item in enumerate(nums):
if i == 0:
max_dict[i] = item
else:
if max_dict[i-1] > 0:
max_dict[i] = max_dict[i-1] + item
else:
max_dict[i] = item
max_num = max(max_dict.values())
return max_num
别人程序：
def maxSubArray_v2(self, nums):
if max(nums) < 0:
return max(nums)
global_max,local_max = float('inf'), 0
for item in nums:
local_max = max(0, local_max+item)
global_max = max(global_max, local_max)
return global_max
比较精炼，不拖泥带水。
DP思想，目标可以分解为一个个小的子目标
62、unique paths
# A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
# The robot can only move either down or right at any point in time.
# The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
# How many possible unique paths are there?
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in xrange(m):
for j in xrange(n):
if i == 0 and j == 0:
dp[i][j] = 1
elif j == 0 and i != 0:
dp[i][j] = dp[i-1][j]
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
注意边界条件，上面的比较好理解，但是不是很GEEK，改进：
def uniquePath_v2(self, m, n):
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
for i in xrange(1, m):
for j in xrange(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
一位数组代替：
def uniquePaths(self, m, n):
if m < n:
return self.uniquePaths(n, m)
ways = [1] * n
for i in xrange(1, m):
for j in xrange(1, n):
ways[j] += ways[j - 1]
return ways[n - 1]
上面的方法极大降低了空间复杂度，只用来保存一维数组信息。以3*3为例，从第二行第二列开始，到当前位置的方式有a[1] = a[1] + a[1-1] 种。本质上，ways[j] += ways[j - 1]中，waya[i-1]表示的是从左边过来的路径，waya[i]表示从上边过来的路径，符合dp[i][j] = dp[i - 1][j] + dp[i][j - 1]内涵，只是不断进行刷新。
63、unique path2
# Follow up for "Unique Paths":
# Now consider if some obstacles
# are added to the grids. How many unique paths would there be?
# An obstacle and empty space is marked as 1 and 0 respectively in the grid.
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if obstacleGrid == []:
return 0
m = len(obstacleGrid)
n = len(obstacleGrid[0])
obstacleGrid[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
for j in range(1, n):
obstacleGrid[0][j] = obstacleGrid[0][j-1] * (1-obstacleGrid[0][j])
for i in range(1, m):
obstacleGrid[i][0] = obstacleGrid[i-1][0] * (1-obstacleGrid[i][0])
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
obstacleGrid[i][j] = 0
else:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
return obstacleGrid[m-1][n-1]
64、min path sum
常规解法：
# Given a m x n grid filled with non-negative numbers, find a path from top
# left to bottom right which minimizes the sum of all numbers along its path.
# Note: You can only move either down or right at any point in time.
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
res = [[0 for _ in xrange(n)] for _ in xrange(m)]
res[0][0] = grid[0][0]
for i in xrange(1, m):
res[i][0] = res[i-1][0] + grid[i][0]
for j in xrange(1, n):
res[0][j] = res[0][j-1] + grid[0][j]
for i in xrange(1, m):
for j in xrange(1, n):
res[i][j] = min(res[i-1][j], res[i][j-1]) + grid[i][j]
return res[m-1][n-1]
def minpathsum2(self,grid):
'''
一维数组简化方法
'''
res = grid[0]
m, n = len(grid), len(grid[0])
for j in xrange(1, n):
res[j] = res[j-1] + grid[0][j]
for i in xrange(1, m):
res[0] = res[0] + grid[i][0]
for j in xrange(1, n):
res[j] = min(res[j], res[j-1]) + grid[i][j]
return res[-1]
总结：
对于62,63,64这一类问题，能很容易想到是用动态规划思想，但是要确保解的质量。常规方法是先构建一个二维数组，依次保存前面子问题的解，进而为最终答案铺垫，二维数组分析要考虑边界条件，即是一维横向量或者一维列向量。后面就可以直接利用递归方程。
常用的第二种方法就是减少空间复杂度，用一个一维数组保存前面子问题的解。
70、climbing stairs
# You are climbing a stair case. It takes n steps to reach to the top.
# Each time you can either climb 1 or 2 steps.
# In how many distinct ways can you climb to the top?
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:
return n
res = [0 for _ in xrange(n+1)]
res[1] = 1
res[2] = 2
for i in xrange(3, n+1):
res[i] = res[i-1] + res[i-2]
return res[n]
def climbStairs2(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:
return n
a = 1
b = 2
for i in xrange(3, n+1):
a, b = b, a + b
return b
def climbStairs3(self, n):
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
91、decode ways
# A message containing letters from A-Z is being
# encoded to numbers using the following mapping:
# 'A' -> 1
# 'B' -> 2
# ...
# 'Z' -> 26
# Given an encoded message containing digits, determine the total number of ways to decode it.
# For example,
# Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
# The number of ways decoding "12" is 2.
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s == '' or s[0] == '0':
return 0
if '00' in s:
return 0
res = [1 for _ in xrange(len(s))]
for i, c in enumerate(s):
if i == 0:
continue
if c == '0':
if s[i-1] > '2':
return 0
else:
res[i] = res[i-2]
else:
if s[i-1] > '2' or s[i-1] == '0':
res[i] = res[i-1]
elif s[i-1] == '2' and c > '6':
res[i] = res[i - 1]
else:
res[i] = res[i-1] + res[i-2]
return res[-1]
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0 or s[0] == '0':
return 0
prev, prev_prev = 1, 0
for i in xrange(len(s)):
cur = 0
if s[i] != '0':
cur = prev
if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')):
cur += prev_prev
prev, prev_prev = cur, prev
return prev
写出的代码不够pythonic，第一种是自己的方法，基本主线是DP，和climbing stairs很像，当前decode的可能性是前面字符和前前面字符可能性之和。但是有限制条件，正常情况下，[12123]，对于3，可能性是res[1212]+res[121]，因为3和23都可以单独解码。但是考虑其他情况，对当前字符为0，则只能和前面结合才能解码，也就是对[121230]，对于0来说，res=res[1212]，同样还有前面字符大于2时，也只有一种结合情况。当然还要考虑其他情况，比如起始字符为0则无解等。这也是自己程序判断的准则。
第二种解法比较精妙，只使用三个变量，方法还是有点绕，MARK。
120、triangle
# Given a triangle, find the minimum path sum from top to
# bottom. Each step you may move to adjacent numbers on the row below.
# For example, given the following triangle
# [
# [2],
# [3,4],
# [6,5,7],
# [4,1,8,3]
# ]
# The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
depth = len(triangle)
if depth == 1:
return triangle[0][0]
for i in xrange(1, depth):
for j in xrange(0, i+1):
if j == 0:
triangle[i][j] += triangle[i - 1][j]
elif j == i:
triangle[i][j] += triangle[i - 1][j-1]
else:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
return min(triangle[depth-1])
121、best time sell and buy stocks
# Say you have an array for which the ith element is the price of a given stock on day i.
# If you were only permitted to complete at most one transaction (ie, buy one and sell
# one share of the stock), design an algorithm to find the maximum profit.
# Example 1:
# Input: [7, 1, 5, 3, 6, 4]
# Output: 5
#
# max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be
# larger than buying price)
# Example 2:
# Input: [7, 6, 4, 3, 1]
# Output: 0
# In this case, no transaction is done, i.e. max profit = 0.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) < 2:
return 0
max_pro, min_price = 0, float('inf')
for price in prices:
min_price = min(price, min_price)
max_pro = max(max_pro, price-min_price)
return max_pro
想一下，这个题简单在于只需要操作依次，也就是说买入一次和卖出一次，使获利最大。最简单就是暴力法，每次取出一个元素，然后后面的找差值最大的。
两个指针是可行的，从前往后和从后往前。可行吗，和11题是有不一样的。当方法不对时，所谓思考都是低质量，还是没有见多识广。问题表述为从所有的数字中找到差值最大的两个数，且保证小值在大值前面。可是为什么能想到这种方法。
139. Word Break
题意是能否将一个单词分成指定列表中的单词的拼接，最先想到的方法是递归。
# Given a non-empty string s and a dictionary wordDict containing
# a list of non-empty words, determine if s can be segmented into
# a space-separated sequence of one or more dictionary words.
# You may assume the dictionary does not contain duplicate words.
#
# For example, given
# s = "leetcode",
# dict = ["leet", "code"].
#
# Return true because "leetcode" can be segmented as "leet code".
#
# UPDATE (2017/1/4):
# The wordDict parameter had been changed to a list of strings
# (instead of a set of strings). Please reload the code definition
# to get the latest changes.
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
if len(s) == 1:
if s in wordDict:
return True
if s == '':
return True
for i in xrange(1, len(s)+1):
if s[:i] in wordDict:
# if i == len(s)-1:
# return True
res = self.wordBreak(s[i:], wordDict)
if res is True:
return True
else:
continue
return False
def wordBreak2(self, s, wordDict):
dp = [False for _ in xrange(len(s)+1)]
dp[-1] = True
# print dp[0]
for i in xrange(0, len(s)):
if i == 0:
if s[i] in wordDict:
dp[i] = True
for j in xrange(0, i+1):
if s[j:i+1] in wordDict and dp[j-1] is True:
dp[i] = True
continue
return dp[len(s)-1]
递归做到超时了。看来还是不行。
动态规划，最重要的是找出子问题方程，类似于最少硬币问题，问题可以分解为dp(i) = dp(j) && s[j, i) in dict。
简单描述下思考过程：迭代整个字符串，对当前字符串，再次从头开始循环，找出前面break point，说明当前能够分解。
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
n = len(s)
max_len = 0
for string in wordDict:
max_len = max(max_len, len(string))
can_break = [False for _ in xrange(n + 1)]
can_break[0] = True
for i in xrange(1, n + 1):
for l in xrange(1, min(i, max_len) + 1):
if can_break[i-l] and s[i-l:i] in wordDict:
can_break[i] = True
break
return can_break[-1]
152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
怎么思考这个问题呢，注意是连续，而且有正负，当前元素保留到本元素的最大正值和最大负值，也就是保存最大值和最小值，根据这个想法得到的答案为：
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
max_pro = [0 for _ in xrange(length)]
min_pro = [0 for _ in xrange(length)]
for i in xrange(length):
if i == 0:
max_pro[i] = nums[i]
min_pro[i] = nums[i]
else:
max_pro[i] = max(max_pro[i - 1] * nums[i], min_pro[i - 1] * nums[i], nums[i])
min_pro[i] = min(max_pro[i - 1] * nums[i], min_pro[i - 1] * nums[i], nums[i])
return max(max_pro)
运行效率为22%，有点低，实际上可以优化，首先，两个列表根本没有这个必要，因为只需要用到前面的一个数即可，而且再者用一个局部变量保存全局的最大值，不用后面的max（）操作。
def maxProduct2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_pro, min_pro = nums[0], nums[0]
glo_max = nums[0]
for num in nums[1:]:
max_pro, min_pro = max(max_pro * num, min_pro * num, num), \
min(max_pro * num, min_pro * num, num)
if max_pro > glo_max:
glo_max = max_pro
return glo_max
经过上面的精简，效率达到了73%
还有以下的参考答案：
class Solution2:
# @param A, a list of integers
# @return an integer
def maxProduct(self, A):
global_max, local_max, local_min = float("-inf"), 1, 1
for x in A:
local_max = max(1, local_max)
if x > 0:
local_max, local_min = local_max * x, local_min * x
else:
local_max, local_min = local_min * x, local_max * x
global_max = max(global_max, local_max)
return global_max
加上了人工判断，简化了调用 min和max函数。
198. House Robber
入室抢劫，问题描述比较简单，一个列表表示每家能够偷的钱财，现在限制为不能连续抢劫两家，否则会报警。如何安排才能使抢劫到的钱财最多。
在大框架下面知道要用动态规划，如何自己分析出最可能的最优方案，首先是求约束条件下整体的最优解，前面的选择会影响到后面，但是当前子问题的只与前面一个或者前面有限个子问题的解有关。问题思路慢慢浮出水面，对于每一家，都有两个选择，抢或者不抢，保存对应的目前最优解。而且两种情况一定要小心分析，当选择抢，则前一家肯定是不能抢的，也就是 rob[i] = notrob[i-1] + nums[i] ，当选择不抢时，前面一家可以抢，也可以不抢，一定要注意，比如[4,1,2,8]，对于2来说，不抢2不一定代表前面1要抢，最优是notrob[i] = max(rob[i],notrob[i])。
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l <= 2:
return max(nums)
rob, notrob = nums[1], nums[0]
for i in xrange(2, l):
rob, notrob = nums[i] + notrob, max(rob, notrob)
return max(rob, notrob)
def rob1(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l < 2:
return nums[0]
pre_max, pre_premax = max(nums[0], nums[1]), nums[0]
for i in nums[2:]:
rob, not_rob = i + pre_premax, pre_max
pre_premax, pre_max = pre_max, max(rob, not_rob)
return max(pre_max, pre_premax)
def rob2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last, now = 0, 0
for i in nums:
last, now = now, max(last + i, now)
return now
第二种解法符合常规逻辑，是典型的动态规划思想，
res[i] = max(res[i-1],res[i-2]+nums[i])，res保存的是到某个房屋是的最大收益。有以下两种情况：
- 如果选择了抢劫上一个屋子，那么就不能抢劫当前的屋子，所以最大收益就是抢劫上一个屋子的收益
- 如果选择抢劫当前屋子，就不能抢劫上一个屋子，所以最大收益是到上一个屋子的上一个屋子为止的最大收益，加上当前屋子里有的钱。
所以，我们只要判断一下两个里面哪个大就行了，同时也是我们的递推式。另外我们可以做一点优化，本来我们是要用一个dp数组来保存之前的结果的。但实际上我们只需要上一次和上上次的结果，所以可以用两个变量就行了。
第一种方法和第二种方法只是表述上不一样，本质是一样的，第一种方法保存的是每次抢和不抢的收益，从过程考虑。而第二种方法保存的是本次和前一次的最大收益，不在乎抢还是不抢，从结果考虑。
第三种解法确实比较逆天，咋看毫无逻辑可言，实际上，精髓在于now表示当前的最大值，管抢还是不抢，last保存上一次的最大值，有这个值就是max()中不抢的来源，而last+i则表示上一次不抢而这次抢了。有点绕，挺有道理的。
213、house robber II
在上一题上升级，就是加入了一个约束条件，就是说第一个和最后一个不能都抢，主要思想还是没有变，引入的难点在于当最后一个抢时结果最大，如何确定第一个抢了没。最容易想到的方法就是第一个house时就给定限制，抢时最终结果如何，以及不抢最终结果如何，对比出最大的。
可以预见到，分不同情况考虑会比较繁琐，实际上转化为俩个类似的问题，一是抢第一家到倒数第二家以及抢不抢第一家到最后一家。
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l < 2:
return nums[0]
pre_max, pre_premax = nums[1], 0
for i in nums[2:]:
rob, not_rob = i + pre_premax, pre_max
pre_premax, pre_max = pre_max, max(rob, not_rob)
a = max(pre_max, pre_premax)
pre_max, pre_premax = nums[0], nums[0]
for i in nums[2:-1]:
rob, not_rob = i + pre_premax, pre_max
pre_premax, pre_max = pre_max, max(rob, not_rob)
b = max(pre_max, pre_premax)
return max(a, b)
这道题只能从上一题的第二种方法出发比较好解，如何从抢和不抢定义收益，会引起连锁反应，导致第一种方法失效。
221. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
二进制矩阵，找到最大的正方形，并返回其面积。
明显，求最终问题可以划分为一个个子问题， 一个子问题可以由上一个子问题推出。最重要的是找出递推公式，可以发现，一个正方形的最右下角的元素，如果它的上方、左方和左上方都是另一个正方形的右下角元素，则组成另一个正方行，边长加1.
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix == [] or matrix == [[]]:
return 0
m = len(matrix)
n = len(matrix[0])
maxsquare = 0
for i in xrange(m):
matrix[i][0] = int(matrix[i][0])
if matrix[i][0] == 1:
maxsquare = 1
for j in xrange(n):
matrix[0][j] = int(matrix[0][j])
if matrix[0][j] == 1:
maxsquare = 1
for i in xrange(1, m):
for j in xrange(1, n):
matrix[i][j] = int(matrix[i][j])
if matrix[i][j]:
matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]) + 1
if matrix[i][j] > maxsquare:
maxsquare = matrix[i][j]
return maxsquare**2
264. Ugly Number II
找丑数，丑数的定义是只能被2，3，5整除，也就是因子只能是2，3，5. 1特殊算是第一个丑数，求出第n个丑数。
如何去思考这个问题，在知道DP求解的前提下，如何由上一个子问题推出。整个问题不是很难，容易被自己思维限制住，从最小的数开始依次乘2，3，5，并更新指针到下一个数，如何取出最小的数呢，
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
uglynum = [1 for _ in xrange(n)]
i = 0
k2 = k3 = k5 = 0
while i < n-1:
minnum = min(uglynum[k2]*2, uglynum[k3]*3, uglynum[k5]*5)
i += 1
uglynum[i] = minnum
if minnum == uglynum[k2]*2:
k2 += 1
if minnum == uglynum[k3]*3:
k3 += 1
if minnum == uglynum[k5]*5:
k5 += 1
return uglynum[n-1]
上面是比较常规的方法，下面是借助堆思想，增加了复杂度，但是比较简洁。堆结构会自动将数据排序，保证堆顶为最小元素。
import heapq
class Solution:
# @param {integer} n
# @return {integer}
def nthUglyNumber(self, n):
ugly_number = 0
heap = []
heapq.heappush(heap, 1)
for _ in xrange(n):
ugly_number = heapq.heappop(heap)
if ugly_number % 2 == 0:
heapq.heappush(heap, ugly_number * 2)
elif ugly_number % 3 == 0:
heapq.heappush(heap, ugly_number * 2)
heapq.heappush(heap, ugly_number * 3)
else:
heapq.heappush(heap, ugly_number * 2)
heapq.heappush(heap, ugly_number * 3)
heapq.heappush(heap, ugly_number * 5)
return ugly_number
def nthUglyNumber2(self, n):
ugly = [1]
i2 = i3 = i5 = 0
while len(ugly) < n:
while ugly[i2] * 2 <= ugly[-1]: i2 += 1
while ugly[i3] * 3 <= ugly[-1]: i3 += 1
while ugly[i5] * 5 <= ugly[-1]: i5 += 1
ugly.append(min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5))
return ugly[-1]
def nthUglyNumber3(self, n):
q2, q3, q5 = [2], [3], [5]
ugly = 1
for u in heapq.merge(q2, q3, q5):
if n == 1:
return ugly
if u > ugly:
ugly = u
n -= 1
q2 += 2 * u,
q3 += 3 * u,
q5 += 5 * u,
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
首先想到的是硬币问题，从第一个数开始遍历到n，每个保存自己最小的完全平方数个数。
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0 for _ in xrange(n+1)]
for i in xrange(1, n+1):
numlist = self.subnum(i)
dp[i] = min(dp[i-num*num] for num in numlist) + 1
return dp[n]
def subnum(self, num):
numlist = []
for i in xrange(1, num+1):
if i*i <= num:
numlist.append(i)
else:
return numlist
return numlist
这个方法比较普通，跑出来性能为33%，第二种方法比较高效
class Solution(object):
_num = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
num = self._num
while len(num) <= n:
num += min(num[-i*i] for i in xrange(1, int(len(num)**0.5+1))) + 1,
return num[n]
其实，受第二种方法的启发，第一种稍作变形为：
class Solution1(object):
dp = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
length = len(self.dp)
while length < n+1:
numlist = self.subnum(length)
temp = min(self.dp[length-num*num] for num in numlist) + 1
length += 1
self.dp.append(temp)
return self.dp[n]
def subnum(self, num):
numlist = []
for i in xrange(1, num+1):
if i*i <= num:
numlist.append(i)
else:
return numlist
return numlist
性能提升到88%，通过缓存来提升效率。在编程中也经常用到这个思想。回头看第二种解法，其实本质一样，通过xrange(1, int(len(num)**0.5+1)))代替了第一种方法中的辅助函数。
300. Longest Increasing Subsequence
最长递增子序列，算是比较经典的一个题，在一串数字中找到最长的递增子序列。常规DP想法，问题的解可以由前面的子问题一步一步求出，对列表进行遍历，依次保存到目前为止比当前数据小的最大数据个数，并保存其中的最大值。
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length < 2:
return length
res = [1 for _ in xrange(length)]
maxLIS = 0
for i in xrange(1, length):
num = self.searchfirst(nums[:i], nums[i], res)
res[i] = num + 1
if res[i] > maxLIS:
maxLIS = res[i]
return maxLIS
# 找出前面比当前数字小的最大长度
def searchfirst(self, nums, item, res):
num = 0
for i in xrange(len(nums)):
if nums[i] < item:
num = max(num, res[i])
return num
更多其他的解法
# Binary search solution.
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
LIS = []
def insert(target):
left, right = 0, len(LIS) - 1
# Find the first index "left" which satisfies LIS[left] >= target
while left <= right:
mid = left + (right - left) / 2;
if LIS[mid] >= target:
right = mid - 1
else:
left = mid + 1
# If not found, append the target.
if left == len(LIS):
LIS.append(target);
else:
LIS[left] = target
for num in nums:
insert(num)
return len(LIS)
# Time: O(n^2)
# Space: O(n)
# Traditional DP solution.
class Solution2(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [] # dp[i]: the length of LIS ends with nums[i]
for i in xrange(len(nums)):
dp.append(1)
for j in xrange(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) if dp else 0
第三种方法其实就是第一种，第一种稍微复杂化了点。二叉树搜索值得进一步深入。
