目录

• 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

第三种方法其实就是第一种，第一种稍微复杂化了点。二叉树搜索值得进一步深入。