Leetcode题解 - 动态规划

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是动态规划相关题目题解总结。

[TOC]

动态规划

递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是动态规划保存了子问题的解，避免重复计算。

动态规划与分治算法类似，都是通过组合子问题的解来求解原问题的：

• 分治算法将问题划分为互不相关的子问题，再递归地求解子问题，最后将它们的解组合起来，求出原问题的解。
• 动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方法会做许多不必要的工作，需要反复求解那些公共子问题，而动态规划对于每个子子问题只求解一次，将其保存在一个表格里面，从而无需每次求解一个子子问题时都需要重新计算，避免了不必要的计算工作。

动态规划的应用场景

• 动态规划方法一般用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优值。

动态规划的一般步骤

• 定义一个状态，这是一个最优解的结构特征；
• 进行状态递推，得到递推公式；
• 进行初始化；
• 返回结果。

动态规划的实质就是分治思想和解决冗余。将原来具有指数级复杂性的算法改进成具有多项式时间的算法，这是动态规划算法的目的。由于在实现的过程中，需要存储各种状态，所以它的空间复杂性要大于其他算法，这是一种以空间换时间的技术。

动态规划三要素

最优子结构性质、子问题重叠性、自底向上的求解方法。

最优子结构性质

• 最优子结构性质，就是问题的最优解包含其子问题的最优解。如果不具备该性质，就不能使用动态规划来解决。常用反证法分析论证问题是否具备最优子结构的性质；
• 有时对某个子问题的解不一定达到最优，但是当把它延伸成整个问题的解时反而成了最优解，这种问题不满足最优子结构性质，无法使用动态规划。

子问题重叠性质

• 动态规划对每个子问题只求解一次，并把其答案保存在表格里，因此可以避免重复计算；
• 子问题重叠性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。

自底向上的求解方法

由于动态规划解决的问题具有子问题重叠的问题，求解时需要自底向上的方法：

• 首先选择合适的表格（一维或二维），将递归的停止条件填入表格的相应位置；
• 然后将问题的规模一级一级放大，求出每一级子问题的最优解，并将其填入表格的相应位置 ；
• 直到问题所要求的规模，此时求出的便是原问题的最优解。

除了自底向上的方法，还可以使用 “带备忘录的自顶向下方法”。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（用数组或列表保存）。当需要子问题的解时，过程首先检查是否已经保存过此解。如果是，直接返回保存的值，从而节省时间；否则，按通常方式计算这个子问题。这个递归过程是带备忘的，因为它记住了之前已经计算出的结果。

贪婪算法的局限性

动态规划的一个关键特点是每次做选择之前，对所有选择的效果进行计算。在计算的结果上选择能够达到最优的选项，从而保证每次选择都是最优的。

但是这种策略在当选项的数量非常巨大的时候将不堪重负。例如下围棋的时候，如果采用动态规划策略，则需要先对每步可能的行棋的影响进行计算，然后比较选择最优的走法。但每一步可行进的走法实在太多，如果再考虑到一盘棋有几乎不计其数的步骤，所以计算任务非常大几乎不可能完成。这种情况就是上面介绍的动态规划的缺点。这个时候应该采用贪婪策略。

贪婪策略运行我们不对所有可能选择的影响计算一遍后作出决策。我们可以在进行选择的时候不进行任何计算，而根据当时的情况作出我们认为最好的选择，这样就避免了大量计算，从而大大提高了算法的效率。

【算法】详解动态规划
算法导论——-动态规划是什么

5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

解题思路

暴力解决

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        maxlen = 0
        start = 0
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                if s[i:j] == s[i:j][::-1] and j-i > maxlen:
                    maxlen = j-i
                    start = i
        if maxlen > 0:
            return s[start:start+maxlen]
        return ''

动态规划

动态规划有两个特点：将大问题拆解为小问题，利用之前的计算结果。

例子：”babad”
新建dp二维数组,
$dp[i][j]=1$
时则说明第i到第j为回文子串。

[[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]]

• 首先计算长度为1的子串，必定是回文；
• 然后判断长度为2的子串，根据相等与否判断是否为回文；
• 到长度为3时，就可以利用上次的计算结果：
  • 如果中心对称的短字符串(去掉头尾，此时只有第2个位置的一个字符)是回文，且如果第1和第3个位置相等，则长字符串也是回文；如果第1和第3个位置不相等，则长字符串不是回文；
  • 如果中心对称的短字符串(去掉头尾)不是回文，则长字符串也不是回文；
• 一直遍历到长度最长的字符串。

即当i=j+1时相邻是为长度为2的情况，当i-j > 2时为长度为3的情况，递推式为：
$dp[i][i] = 1$
$dp[j][i] = (s[i] == s[j]) \& (i-j<=2 | dp[j + 1][i - 1])$

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        dp = [[0]*len(s) for _ in range(len(s))]
        start, end, maxlen = 0, 0, 0
        for i in range(len(s)):
            for j in range(i):
                dp[j][i] = (s[i]==s[j]) & ((i-j<=2) | dp[j+1][i-1])
                if dp[j][i] and maxlen < i-j+1:
                    maxlen = i-j+1
                    start = j
                    end = i
            dp[i][i] = 1
        return s[start:end+1]

53. 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

动态规划：
当我们想要获得0~n中最大的子串和时，如果0~n-1的连续和小于0，则连续和等于它自己nums[n]，如果为正，则连续和等于它自己加上0~n-1的连续和。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        dp = [0]*len(nums)
        dp[0] = nums[0]
        for i in range(1,len(nums)):
            if dp[i-1] < 0:
                dp[i] = nums[i]
            else:
                dp[i] = nums[i] + dp[i-1]
        return max(dp)

temp比0小，那就从开始重新记录

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        res = nums[0]
        temp = 0
        for x in nums:
            temp += x
            if temp > res:
                res = temp
            if temp < 0:
                temp = 0
        return res

讨论区里很精巧的解法。
将每一个nums[i]的值，看成是存放前面连续的和大于0的序列；
通过遍历，纠正错误存放的值；
nums[i]中的每一个数存放的都是序号i前面连续数据的最大和。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        for i in range(1,len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

62. 不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

解题思路

动态规划。

• 当只有一行或者一列的时候，只有一种方式；
• 遍历其余位置，每一个位置只能由其左边或上边的元素达到，即迭代公式为:

• 遍历完成后，dp矩阵存放了每一个位置的走法数，因此返回最后一个数即为所求。

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m < 1 or n < 1:
            return 0
        if m == 1 or n == 1:
            return 1
        dp = [[1]*n for i in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] == 1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

63. 不同路径 II

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解题思路

有障碍物的地方走法为0。

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if len(obstacleGrid) == 0:
            return 0
        
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0]*n for i in range(m)]
        
        for i in range(m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break
        for i in range(n):
            if obstacleGrid[0][i] == 0:
                dp[0][i] = 1
            else:
                break
                
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
                    
        return dp[m-1][n-1]

64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路

每个位置的最小数字总和为当前位置数值加上 上方及左方数字总和 较小的数。

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
        
        m, n = len(grid), len(grid[0])
        dp = [[0]*n for i in range(m)]
        dp[0][0] = grid[0][0]
        
        for i in range(1,m):
            dp[i][0] = grid[i][0] + dp[i-1][0]
        for i in range(1,n):
            dp[0][i] = grid[0][i] + dp[0][i-1]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        
        return dp[m-1][n-1]

70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解题思路

递归 (超时)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

动态规划

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 3:
            return n
        dp = [0]*n
        dp[0] = 1
        dp[1] = 2
        for i in range(2,n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 3:
            return n
        a, b = 1, 2
        res = 0
        for i in range(3, n+1):
            res = a + b
            a, b = b, res
        return res

72. 编辑距离

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解题思路

维护一个二维的数组dp，其大小为 (m+1)x(n+1)，m和n分别为 word1 和word2 的长度。$dp[i][j] $表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤。那我们可以先给这个二维数组dp的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，于是转换步骤完全是另一个字符串的长度。
当$word1[i] == word2[j]$时，$dp[i][j] = dp[i - 1][j - 1]$
当$word1[i] != word2[j]$时，有三种处理方法，首先是直接插入一个 word2[j]，那么 word2[j] 位置的字符就跳过了，接着比较 $word1[i+1]$ 和 $word2[j+1] $即可。第二个种方法是删除，即将 $word1[i]$ 字符直接删掉，接着比较 $word1[i+1]$ 和 $word2[j]$ 即可。第三种则是将 $word1[i]$ 修改为 $word2[j]$，接着比较 $word1[i+1]$ 和 $word[j+1]$ 即可。所以 $dp[i][j]$是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，分别对应的增加，删除，修改操作。
转移方程为：
如果 $word1[i - 1] == word2[j - 1]$, $dp[i][j] = dp[i - 1][j - 1]$
否则 $dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1$

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        
        dp = [[0] * (len(word1)+1) for _ in range(len(word2)+1)]
        
        for i in range(1, len(word1)+1):
            dp[0][i] = i
        
        for i in range(1, len(word2)+1):
            dp[i][0] = i
        
        for i in range(1, len(word2)+1):
            for j in range(1, len(word1)+1):
                if word2[i-1] == word1[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        
        return dp[-1][-1]

91. 解码方法

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解题思路

dp[i]代表解析是s[:i]字符串的所有可能的方式数目。则：

dp[i] = dp[i-1] if s[i] != '0'
       + dp[i-2] if '9' < s[i-2:i] < '27'

举例子：对于’226’：

• 令dp=[0,0,0,0]，初始化为[1,0,0,0]；
• 从第一个位置开始，输入’2’，不为0，dp=[1,1,0,0]；
• 第二个位置为’2’，不为0，所以dp=[1,1,1,0]，此时前两位为’22’，满足区间，所以变为[1,1,2,0];
• 第三个位置为’6’，不为0，所以dp=[1,1,2,2]，此时前两位为’26’，满足区间，所以变为[1,1,2,3]。

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        dp = [0] * (len(s)+1)
        dp[0] = 1
        for i in range(1, len(s)+1):
            if s[i-1] != '0':
                dp[i] = dp[i-1]
            if i != 1 and '09' < s[i-2:i] < '27':
                dp[i] += dp[i-2]
        return dp[len(s)]

96. 不同的二叉搜索树

题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

解题思路

给定一个数n，求1到n这些数可以构成多少棵二叉树。
给定一个序列1.....n，为了构造所有二叉树，我们可以使用1......n中的每一个数i作为根节点，自然1......(i-1)必然位于树的左子树中，(i+1).....n位于树的右子树中。然后可以递归来构建左右子树，由于根节点是唯一的，所以可以保证构建的二叉树都是唯一的。

使用两个状态来记录：

dp(n)：长度为n的序列的所有唯一的二叉树。

dp(i,n)，1<=i<=n：以i作为根节点的二叉树的数量。

dp(n)就是我们要求解的答案，dp(n)可以由F(i,n)计算而来。

dp(n)=F(1,n)+F(2,n)+...+F(n,n)                           (1)

dp(0)=1,dp(1)=1

对于给定的一个序列1.....n，我们取i作为它的根节点，那么以i作为根节点的二叉树的数量F(i)可以由下面的公式计算而来：

F(i,n)=dp(i-1)*dp(n-i-1) 1<=i<=n                            (2)

比i小的数1...i-1作为左子树，比i大的数i+1...n作为右子树，左子树的排列和右子树的排列的乘积是此时的数目。

例如 i=3，n=3时， dp[3] = dp[0]*dp[2]+dp[1]*dp[1]+dp[2]dp[0]。即左右子树节点数量分别为(0,2),(1,1),(2,0)。

综合公式（1）和公式（2），可以看出：

dp(n) = dp(0) * dp(n-1) + dp(1) * dp(n-2) + … + dp(n-1) * dp(0)

[参考](https://blog.csdn.net/u012501459/article/details/46622501)

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1,1,2]
        if n <= 2:
            return dp[n]
        dp += [0] * (n-2)
        for i in range(3, n+1):
            for j in range(i):
                dp[i] += dp[j]*dp[i-j-1]
        return dp[n]

95. 不同的二叉搜索树 II

题目描述

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

解题思路

• 遍历1~n选择一个数当作根节点，所以其左边的数字构成左子树，右边的数字构成右子树。
• 当左子树固定的时候，把所有可能的右子树都构成，然后再变换左子树。（两层for循环遍历leftnodes和rightnodes）。

# 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 generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n <= 0:
            return []
        return self.dfs(1, n+1)
    
    def dfs(self, left, right):
        res = []
        for rootval in range(left, right):
            leftnodes = self.dfs(left, rootval) or [None]
            rightnodes = self.dfs(rootval+1, right) or [None]
            for leftnode in leftnodes:
                for rightnode in rightnodes:
                    root = TreeNode(rootval)
                    root.left = leftnode
                    root.right = rightnode
                    res.append(root)
        return res

120. 三角形最小路径和

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

解题思路

新建dp和三角形一样大小，dp[i][j]为第i层第j个位置的最短路径，dp初始化为最下面一层，从倒数第二层自底向上遍历，则：

dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0:
            return 0
        
        dp = []
        for i in range(len(triangle)):
            dp.append([0]*len(triangle[i]))    
        
        dp[-1] = triangle[-1]
        for i in range(len(triangle)-2, -1, -1):
            for j in range(i+1):
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
        return dp[0][0]

由于 $dp[i][j]$ 只被用了一次，所以可以变为一维dp：

dp[i] = min(dp[i],dp[i+1]) + triangle[i][j]

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 0:
            return 0
        
        dp = triangle[-1]
        for i in range(len(triangle)-2, -1, -1):
            for j in range(i+1):
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        return dp[0]

121. 买卖股票的最佳时机

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

维护两个变量，到目前为止的最小值和最大收益。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        maxprofit = 0
        minprice = prices[0]
        for i in range(1, len(prices)):
            minprice = min(minprice, prices[i])
            maxprofit = max(maxprofit, prices[i]-minprice)
        return maxprofit

动态规划
dp[i]为前i天的最大收益 = max(前i-1天的最大收益，第i天的价格-前i-1种的最小价格)

dp[i] = max(dp[i-1]-min(prices[:i])

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        dp = [0]*len(prices)
        for i in range(1,len(prices)):
            dp[i] = max(dp[i-1], prices[i]-min(prices[:i]))
        return dp[-1]

122. 买卖股票的最佳时机 II

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

当今天价格比昨天价格高时，就做一次交易。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        maxprofit = 0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                maxprofit += prices[i]-prices[i-1]
        return maxprofit

动态规划，dp[i]为到第i天的最大收益，当今天价格比昨天价格高时，就做一次交易，dp[i] = dp[i-1]+prices[i]-prices[i-1] if prices[i]>prices[i-1] else 0.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        dp = [0] * len(prices)
        for i in range(1,len(prices)):
            dp[i] = dp[i-1]
            if prices[i] > prices[i-1]:
                dp[i] += prices[i]-prices[i-1]
        return dp[-1]

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "Leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "Leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路

dp[i]代表的时[0,i)满不满足单词拆分，需要遍历的范围为1~N+1，dp[0]初始化为True。
两层循环，外层循环遍历每个位置的状态，内层判断前面是否有一个位置j的状态为真 and 位置j到当前位置i是否在wordDict中。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return True
        
        if len(wordDict) == 0:
            return False
        
        dp = [False] * (len(s)+1)
        dp[0] = True
        
        for i in range(1,len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
        return dp[-1]

152. 乘积最大子序列

题目描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

暴力，超时。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        res = nums[0]
        for i in range(len(nums)):
            res = max(res, nums[i])
            cur = nums[i]
            
            for j in range(i+1,len(nums)):
                cur *= nums[j]
                res = max(res, cur)
                
        return res

动态规划

考虑某个位置出现负数或0的情况。当遇到0时，整个乘积变为0；当遇到负数时，当前的最大乘积变为最小乘积，最小乘积变为最大乘积。

使用两个数组分别记录以某个位置i结尾时的最大乘积和最小乘积，另最大乘积为dpmax，最小乘积为dpmin：

• 当前最大值为已知最大值乘当前值，当前值，已知最小值乘当前值，三者中的最大值；
• 当前最小值为已知最小值乘当前值，当前值，已知最大值乘当前值，三者中的最小值；
• 结果为最大值数组中的最大值。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        dpmin = [0]*len(nums)
        dpmax = [0]*len(nums)
        
        dpmin[0] = dpmax[0] = nums[0]
        res = nums[0]
        for i in range(1,len(nums)):
            dpmin[i] = min(dpmax[i-1]*nums[i], nums[i], dpmin[i-1]*nums[i])
            dpmax[i] = max(dpmax[i-1]*nums[i], nums[i], dpmin[i-1]*nums[i])
            res = max(res, dpmax[i])
        # return max(dpmax)
        return res

空间优化。

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
                
        dpmin = dpmax = nums[0]
        res = nums[0]
        for i in range(1,len(nums)):
            lastmin = dpmin
            lastmax = dpmax
            dpmin = min(lastmax*nums[i], nums[i], lastmin*nums[i])
            dpmax = max(lastmax*nums[i], nums[i], *nums[i])
            res = max(res, dpmax)
        return res

198. 打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路

动态规划，维护一个长为len(nums)的数组dp，dp[i]代表在i处能取得的最大金额，这个房子该不该偷，这么决定的因素是这个房子偷了的话的收益和不偷留着偷下一个房子的收益那个比较高：

• 房子i的金额+dp[i-2]的金额 大于 dp[i-1]时，偷；
• 房子i的金额+dp[i-2]的金额 小于 dp[i-1]时，不偷。

即递推式为：

dp[0] = nums[0]    
dp[1] = nums[1]    
dp[i] = max(dp[i-2]+nums[i], dp[i-1])

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(dp[0], nums[1])
        
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        
        return dp[-1]

213. 打家劫舍 II

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

解题思路

本题相比第198题就多了不同时偷第一个和最后一个的约束条件。所以，两种偷的情况：第一种不偷最后一个房间，第二种不偷第一个房间，求这两种偷法能获得的最大值。

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) ==  0:
            return 0
        if len(nums) <= 2:
            return max(nums)
        
        return max(self.helper(nums[:len(nums)-1]), self.helper(nums[1:]))
    
    def helper(self, nums):
        if len(nums) == 2:
            return max(nums)
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(dp[0], nums[1])
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        return dp[-1]

221. 最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

解题思路

使用DP，设DP[i][j]为以i,j位置为右下角顶点的能构成的最大正方形的边长，DP数组的第一行和第一列和matrix相等，其他位置当matrix[i][j]==1时，能构成的正方形边长等于左边，上边，左上角能构成正方形边长的最小值+1.
递推公式：

1 when i==0 or j == 0, dp[i][j] = matrix[i][j]
2 when i > 0 and j > 0, 
             if matrix[i][j] == 0  dp[i][j] = 0
             if matrix[i][j] == 1  dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

参考

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        
        if len(matrix) == 0:
            return 0
        
        dp = [[0]*len(matrix[0]) for i in range(len(matrix))]
        
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == 0 or j == 0:
                    dp[i][j] = 1 if matrix[i][j] == '1' else 0
                elif matrix[i][j] == '1':
                    dp[i][j] = 1+ min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
                res = max(res, dp[i][j])     
        
        return res*res

264. 丑数 II

题目描述

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。
n 不超过1690。

解题思路

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n <= 6:
            return n
        
             
        dp = [1]
        t2, t3, t5 = 0, 0, 0
        
        for i in range(1, n):
            dp.append(min(dp[t2]*2, dp[t3]*3, dp[t5]*5))
            if dp[t2]*2 == dp[-1]:
                t2 += 1
            if dp[t3]*3 == dp[-1]:
                t3 += 1
            if dp[t5]*5 == dp[-1]:
                t5 += 1
        
        return dp[-1]

279. 完全平方数

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解题思路

dp[i] = 1+min(dp[i-1^2],dp[i-2^2],…,dp[i-k^2])

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n == 0:
            return 1

        dp = [0]*(n+1)
        
        for i in range(1, n+1):
            minval = float('inf')
            for j in range(1, int(i**0.5)+1):
                minval = min(minval, dp[i-j*j])
            dp[i] = minval + 1
        
        return dp[-1]

四平方数定理
https://github.com/grandyang/Leetcode/issues/279

class Solution:
    def numSquares(self, n: int) -> int:
        
        if n == 0:
            return 0
        
        while n % 4 == 0:
            n //= 4
            
        if n % 8 == 7:
            return 4
        
        for i in range(int(n**0.5)+1):
            j = int((n - i*i)**0.5)
            if i*i + j*j == n:
                if i != 0 and j != 0:
                    return 2
                else:
                    return 1
        return 3

300. 最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。
• 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路

使用dp保存包目前为止的最大递增子序列长度，最后求所有为止的最大值，而不是dp的最后元素
1初始化dp[i]=1
2对每一个位置，如果当前位置比之前位置的大，则此时为递增子序列，更新之

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) <= 1:
            return len(nums)
        
        res = 1
        dp = [1]*len(nums)
        
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    res = max(res, dp[i])
                
        return res

303. 区域和检索 - 数组不可变

题目描述

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

• 你可以假设数组不可变。
• 会多次调用 sumRange 方法。

解题思路

先把到当前位置的和求出来，然后再调用的时候直接右边的和减去左边的和。

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.data = []
        total = 0
        for num in nums:
            total += num
            self.data.append(total)

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        
        if i == 0:
            return self.data[j]
        else:
            return self.data[j]-self.data[i-1]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

304. 二维区域和检索 - 矩阵不可变

题目描述

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例:

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

说明:

• 你可以假设矩阵不可变。
• 会多次调用 sumRegion 方法。
• 你可以假设 row1 ≤ row2 且 col1 ≤ col2。

解题思路

使用dp保存当前位置到左上角元素构成的矩形的所有元素和，添加了第一列和第一行全是0，这样能保证在求和的时候，每个位置的和是是左边的和+上边的和-左上元素的和+当前位置的值

Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

参考

class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """

        if not matrix or not matrix[0]:
            m, n = 0, 0
        else:
            m, n = len(matrix), len(matrix[0])
        self.dp = [[0]*(n+1) for _ in range(m+1)]
        
        for i in range(m):
            for j in range(n):
                self.dp[i+1][j+1] = self.dp[i+1][j]+self.dp[i][j+1]-self.dp[i][j] + matrix[i][j]
        
    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        
        return self.dp[row2+1][col2+1]-self.dp[row2+1][col1]-self.dp[row1][col2+1]+self.dp[row1][col1]

309. 最佳买卖股票时机含冷冻期

题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

使用两个数组
1 sell[i]表示该天结束之后手里没有股票的情况下的最大收益，可能情况为该天手里有股票卖了，或者该天没进行交易，即 max(hold[i-1]+prices[i]， sell[i-1]);
2 hold[i]表示该天结束之后手里有股票的情况下的最大收益，可能情况为手里有股票但是没进行交易，或者手里没有股票买进股票，今天买进的条件是昨天必须休息，即max(hold[i-1], sell[i-2]-prices[i])。

注意：第一天不可能有卖股票的操作，hold[0] = -prices[0]。

该算法的时间复杂度是O(n)，空间复杂度是O(n)。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0

        sell = [0 for _ in range(len(prices))]
        hold = [0 for _ in range(len(prices))]
        hold[0] = -prices[0]
        
        for i in range(1, len(prices)):
            sell[i] = max(sell[i-1], hold[i-1]+prices[i])
            hold[i] = max(hold[i-1], (sell[i-2] if i>=2 else 0)-prices[i])
        
        return sell[-1]

优化空间复杂度到O(1)

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0

        cursell = 0
        precell = 0
        hold = -prices[0]
        
        for i in range(1, len(prices)):
            
            temp = cursell
            cursell = max(cursell, hold+prices[i])
            hold = max(hold, (presell if i>= 2 else 0)-prices[i])
            presell = temp
        
        return cursell

322. 零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明:

• 你可以认为每种硬币的数量是无限的。

解题思路

DP。构建一个amount+1的数组，保存面额从0到amount+1需要使用的最少硬币数量。
对于每一个位置i，如果j-c >= 0, dp[i] = min(dp[i],dp[i-c]+1)

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        
        if amount == 0:
            return 0
        
        if len(coins) == 0:
            return -1
        
        dp = [float('inf')]*(amount+1)
        dp[0] = 0
        
        for i in range(1, amount+1):
            for c in coins:
                if i-c >= 0:
                    dp[i] = min(dp[i], dp[i-c]+1)
        
        return dp[-1] if dp[-1] != float('inf') else -1

f(n) = min(f(n - c1), f(n - c2), … f(n - cn)) + 1

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        
        if amount == 0:
            return 0
        
        if len(coins) == 0:
            return -1
        
        dp = [0 for _ in range(amount+1)]
        
        for i in range(1, amount+1):
            cost = float('inf')
            for c in coins:
                if i-c >= 0:
                    cost = min(cost, dp[i-c]+1)
            dp[i] = cost
        
        return dp[-1] if dp[-1] != float('inf') else -1

338. 比特位计数

题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

• 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
• 要求算法的空间复杂度为O(n)。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 builtin_popcount）来执行此操作。

解题思路

找规律使用dp，如果i是偶数，它的二进制1的位数等于i//2中1的位数；如果i是奇数，那么它的二进制位数等于i-1的二进制位数+1.
即 if i%2==0: dp[i] = dp[i//2]
else: dp[i] = dp[i-1]+1

又因为i为奇数时，i-1为偶数，即dp[i-1]=dp[i//2]，此时dp[i] = dp[i//2]+1，综合起来可以写成dp[i] = dp[i//2] + (i&1)

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        
        if num < 0:
            return []
        
        dp = [0] * (num+1)
        
        for i in range(1, num+1):
            # if i % 2 == 0:
            #     dp[i] = dp[i//2]
            # else:
            #     dp[i] = dp[i-1] + 1
            
            dp[i] = dp[i//2] + (i&1)
                
        return dp

暴力，时间复杂度为O(n*sizeof(integer))

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        
        if num < 0:
            return []
        
        res = []
        
        for i in range(num+1):
            count = 0
            while i:
                if i&1:
                    count += 1
                i >>= 1
            res.append(count)
        
        return res

343. 整数拆分

题目描述

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

解题思路

使用dp，dp[i]表示i拆分后的最大乘积，将i分为两部分j和i-j，将这两部分相乘取最大的。

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n == 2:
            return 1
        if n == 3:
            return 2
        
        dp = [0]*(n+1)
        dp[2] = 1
        dp[3] = 2
        
        for i in range(4, n+1):
            for j in range(1, i//2 + 1):
                dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
        
        return dp[-1]

357. 计算各个位数不同的数字个数

题目描述

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

示例:

输入: 2
输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

解题思路

//dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1));
//加上dp[i-1]没什么可说的，加上之前的数字
//dp[i-1]-dp[i-2]的意思是我们之前判断各位不重复的数字
//我们要在这些数字后面填新的数字。当i=2时，说明之前选取的数字只有
//1位，那么我们只要与这一位不重复即可，所以其实有9(10-1)种情况（比如1，后面可以跟0,2,3,4,5,6,7,8,9）。
//当i=3时，说明之前选取的数字有2位，那么我们需要与2位不重复，所以剩余的
//有8（10-2）种（比如12，后面可以跟0,3,4,5,6,7,8,9）

class Solution(object):
    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n == 0:
            return 1
        
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 10
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + (dp[i-1]-dp[i-2]) * (10-(i-1))
        
        return dp[-1]

368. 最大整除子集

题目描述

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

解题思路

首先对数组进行排序，使用dp，dp[i]的含义是从0~i位置满足题目的数组最长长度，先用i遍历每个数字，然后用j从后向前（从前到后也可以）寻找能被nums[i]整除的数字，这样如果判断能整除的时候，在判断dp[i]<d[j]+1，即判断对于以i为结尾的最长数组是否变长了。在变长的情况下，需要更新dp[i]，同时使用parent[i]更新i的前面能整除的数字。另外还要统计对于整个数组最长的子数组长度。

知道了对于每个位置最长的子数组之后，我们也就知道了对于0~n区间内最长的满足题目条件的数组，最后需要再次遍历，使用parent就能把正儿个数组统计输出出来。因为这个最大的索引mx_index是对n而言的，所以输出是逆序的。

参考

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if len(nums) == 0:
            return []
        
        nums.sort()
        dp = [0] * len(nums)
        parent = [0] * len(nums)
        maxlen = 0
        maxlenIndex = -1
        
        for i in range(len(nums)):
            for j in range(i-1, -1, -1):
            # for j in range(i):
                if nums[i] % nums[j] == 0 and dp[i] < dp[j]+1:
                    dp[i] = dp[j] + 1
                    parent[i] = j
                    if dp[i] > maxlen:
                        maxlen = dp[i]
                        maxlenIndex = i
        
        res = []
        for i in range(maxlen+1):
            res.append(nums[maxlenIndex])
            maxlenIndex = parent[maxlenIndex]
        
        return res[::-1]

375. 猜数字大小 II

题目描述

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

示例:

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

解题思路

这题要求我们在猜测数字y未知的情况下（1~n任意一个数），要我们在最坏情况下我们支付最少的钱。也就是说要考虑所有y的情况。

我们假定选择了一个错误的数x，（1<=x<=n && x!=y ）那么就知道接下来应该从[1,x-1 ] 或者[x+1,n]中进行查找。 假如我们已经解决了[1,x-1] 和 [x+1,n]计算问题，我们将其表示为solve(L,x-1) 和solve(x+1,n)，那么我们应该选择max(solve(L,x-1),solve(x+1,n)) 这样就是求最坏情况下的损失。总的损失就是 f(x) = x + max(solve(L,x-1),solve(x+1,n))

那么将x从1~n进行遍历，取使得 f(x) 达到最小，来确定最坏情况下最小的损失，也就是我们初始应该选择哪个数。

上面的说法其实是一个自顶向下的过程（Top-down），可以用递归来解决。很容易得到如下的代码（这里用了记忆化搜索）：

参考

class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        dp = [[0]*(n+1) for _ in range(n+1)]
        return self.solve(dp, 1, n)
    
    def solve(self, dp, left, right):
        if left >= right:
            return 0
        if dp[left][right]:
            return dp[left][right]

        dp[left][right] = min(i + max(self.solve(dp, left, i-1), self.solve(dp, i+1, right)) for i in range(left, right+1))
        return dp[left][right]

376. 摆动序列

题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

进阶:
你能否用 O(n) 时间复杂度完成此题?

解题思路

摆动为一升一降，一个up就要配一个down构成一组。
注意去重

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        
        if len(nums) <= 1:
            return len(nums)
        
        up = 1
        down = 1
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1
        
        return max(up, down)

377. 组合总和 Ⅳ

题目描述

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

进阶：

• 如果给定的数组中含有负数会怎么样？
• 问题会产生什么变化？
• 我们需要在题目中添加什么限制来允许负数的出现？

解题思路

使用dp[i]表示组合数为i时使用nums中的数组能组成组合数的个数，因为都是正数，所以长度最多是target,target个1组成。

从1遍历到target，对于每一个数i，遍历nums数组，如果i>=x, dp[i] += dp[i - x]。比如说对于[1,2,3] 4，在计算dp[3]的时候，3可以拆分为1+x，而x即为dp[2]，3也可以拆分为2+x，此时x为dp[1]，3同样可以拆为3+x，此时x为dp[0]，我们把所有的情况加起来就是组成3的所有情况了。

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        if len(nums) == 0:
            return 0

        dp = [0] * (target+1)
        dp[0] = 1
        
        for i in range(1, target+1):
            for x in nums:
                if i >= x:
                    dp[i] += dp[i-x]
        
        return dp[-1]

392. 判断子序列

题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

示例 1:

s = "abc", t = "ahbgdc"

返回 true.

示例 2:

s = "axc", t = "ahbgdc"

返回 false.

后续挑战 :

• 如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

dp的tag不用dp。使用一个指针index记录最后s[:index]在t中存在的最后位置。

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        if len(t) < len(s):
            return False
        if len(s) == 0:
            return True

        index = 0
        for i in range(len(t)):
            if t[i] == s[index]:
                index += 1
                if index == len(s):
                    return True

        return index == len(s)