动态规划

70 爬楼梯

记忆化数组解决：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        memo = [-1 for i in range(n+1)]
        def help(n):
            if n == 0 or n == 1:
                return 1

            if memo[n] == -1:
                memo[n] = help(n-1) + help(n-2)

            return memo[n]

        return help(n)

动态规划解决：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        memo = [-1 for i in range(n+1)]
        memo[0] = 1
        memo[1] = 1
        for i in range(2,n+1):
            memo[i] = memo[i-1] + memo[i-2]
        return memo[n]

120 三角形最小路径和

解法一：既然是从上往下移动，我们可以把上一层的元素的值加到下一层的相邻元素上，如果下一层某个元素在上一层中有两个相邻的元素，那个就把这两个元素中较小的那个加到下一层元素上。（改变三角形中的值）考虑三角形的独特性质

demo1
demo2
demo3

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        n = len(triangle)
        for i in range(1,n):
            triangle[i][0] += triangle[i-1][0]
            triangle[i][i] += triangle[i-1][i-1]

            for j in range(1, i):
                triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j])
        return min triangle[n-1]

解法二：用一个数组保存求值过程，不会改变三角形中的数值,dp数组中在遍历新的一层时候，其值初始为上层的值。

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = [0]*len(triangle)
        dp[0] = triangle[0][0]
        for i in range(1,len(triangle)):
            pre = dp[0] #每行遍历，都要设置新的pre,pre不断变换，代表上层前一个值，dp[j]代表上一层后一个相邻值
            # 注意仔细思考dp和triangle的关系
            for j in range(len(triangle[i])):
                tmp = dp[j]
                if j == 0:
                    dp[j] = pre
                elif j == len(triangle) - 1:
                    dp[j] = pre
                else:
                    dp[j] = min(dp[j],pre)
                dp[j] += triangle[i][j]
                pre = tmp
        return min(dp)

64 矩形 最小路径和

这道题目可以先把网格第一行和第一列填写，不断将前边值累加到后边。最后从(1,1)
坐标开始填写表格，选择min(down,right)加上自身初始值，使其等于(1,1)位置新值。

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid) # row
        n = len(grid[0]) # column

        for j in range(1,n):
            grid[0][j] += grid[0][j-1]
        for i in range(1,m):
            grid[i][0] += grid[i-1][0]

        for i in range(1,m):
            for j in range(1,n):
                grid[i][j] += min(grid[i][j-1],grid[i-1][j]) # down or right
        return grid[m-1][n-1]

343 整数拆分

通过求子问题最优解，可以求解原问题最优解
解法一：记忆化搜索

class Solution:
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        memo = [-1]*(n+1)
        
        def help(n):
            if n == 1:
                return 1
            if memo[n] != -1:
                return memo[n]

            res = -1
            for i in range(1,n):
                res = max(res, i*(n-i),i*help(n-i))
            memo[n] = res
            return res
        return help(n)

解法二：动态规划

class Solution:
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        #memo[i] 表示将数字i分割(至少分割成两部分)后得到的最大乘积
        memo = [-1 for i in range(n+1)]
        memo[1] = 1

        for i in range(2,n+1):#求解memo[i]
            for j in range(1,i):
                memo[i] = max(memo[i] , j*(i-j), j*memo[i-j])
        return memo[n]

279完全平方数(用python会超时)

解法一： 记忆化搜索：

import sys
class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        memo = [-1]*(n+1)
        def help(n,memo):
            if n == 0:
                return 0
            if memo[n] != -1:
                return memo[n]
            res = sys.maxsize # python中最大整数
            i = 1
            while n-i*i >= 0:
                res = min(res,  1 + help(n - i*i , memo))
                i += 1
            memo[n] = res
            return memo[n]
        return help(n,memo)

解法二：动态规划

import sys
class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        memo = [sys.maxsize] *(n+1)
        memo[0] = 0
        for i in range(1,n+1):
            j = 1
            while i-j*j >= 0:
                memo[i] = min(memo[i], 1 + memo[i-j*j])
                j += 1
        return memo[n]

91 解法方法

如果字符串没有“0”,那么每次解析要么1位，要么解析2位。可以看做是爬楼梯问题，然而存在"0",因此考虑如下：解题思路
其中dp(i)表示s[0]到s[i-1]这一共i个字符组成的子串编码个数。
代码实现：
其实我不太明白为什么 dp[0]初始化为1

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0 or s[0] == '0':
            return 0
        dp = [0] * (len(s)+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(1,len(s)):
            tmp = int(s[i-1:i+1])
            if tmp <=26 and tmp >= 10:
                dp[i+1] += dp[i-1]
            if tmp%10 != 0:
                dp[i+1] += dp[i]
        return dp[len(s)]

解法二：

1.PNG

代码实现：

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        # s[0]..s[n-1]
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0
        #初始化很重要
        current = 1#初始A[i-1]为1
        pre = 1 #初始A[i-2]为1

        for i in range(1,n): #从s[1]到s[n-1]
            tmp = current
            if s[i] == '0':
                if s[i-1] == '1' or s[i-1] == '2':
                    current  = pre # A[i] = A[i-2]
                else:
                    return 0
            elif s[i-1] == '1' or s[i-1] == '2' and s[i] <= '6':
                current += pre  # A[i] = A[i-2] + A[i-1]
            else:
                current = current  #A[i] = A[i-1]

            pre = tmp #设置新的A[i-2]

        return current

62 不同路径 unique paths

填一个m*n的矩形，i == 0 or j == 0 时 ，hashmap[(i,j)]均为0
其余位置的点的要么来自上，要么来自左，因此总路径数目得加上左和上两部分就可以求得。
hashmap[(i,j)] = hashmap[(i,j-1)] + hashmap[(i-1,j)]
代码如下：

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        hashmap = {}
        for i in range(m):
            for j in range(n):
                if i==0 or j == 0:
                    hashmap[(i,j)] = 1 #inital the i == 0 and j==0 
                else:
                    hashmap[(i,j)] = hashmap[(i,j-1)] + hashmap[(i-1,j)] # from left or up 
        return hashmap[(m-1,n-1)]

62 不同路径二 unique paths ||

加了障碍，和上题目很类似，只要在障碍处，将值设为1即可。 这里用一维数组记录路径数的变换，记得数组先行后列逐渐更新，最后得到终值。
代码如下：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if obstacleGrid is None:
            return None
        m = len(obstacleGrid)
        if m == 0:
            return 0
        n = len(obstacleGrid[0])
        if n == 0:
            return 0

        dp = [0] * n
        dp[0] = 1 # 首列设置为1
        for i in range(m): #对于第一层循环，执行完后dp中存储的是一层的矩阵值，m层遍历完后，那么存储的是最终的值
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                else:
                    if j != 0:
                        dp[j] += dp[j-1] #dp[j] = dp[j] + dp[j-1]   上加左
        return dp[n-1]

198打家劫舍 House robbery

状态转移方程如图:

1.PNG

f(s)表示偷取(s..n-1)范围内物品的房子
解法一：记忆化搜索

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        memo = [-1] * len(nums)

        def tryRob(nums, index):
            if index >= len(nums):
                return 0
            if memo[index] != -1:
                return memo[index]

            res = 0
            for i in range(index,len(nums)):
                res = max(res, nums[i] +tryRob(nums, i+2))
            memo[index] = res
            return res

        return tryRob(nums,0)

解法二：动态规划

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        if n == 0 :
            return 0

        # memo[i]表示抢nums[i...n)所能获得的最大收益
        #从小到大 在这道题目从后向前
        memo = [0] * n
        memo[n-1] = nums[n-1]
        i = n-2
        while i >= 0:
            for j in range(i,n):
                if j+2 < n:
                    memo[i] = max(memo[i], nums[j]+memo[j+2])
                else:
                    memo[i] = max(memo[i], nums[j]) # n-2, n-1
            i -= 1
        return memo[0]

优化状态转移：

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)

        if n == 0 :
            return 0

        # memo[i]表示抢nums[i...n)所能获得的最大收益
        #从小到大 在这道题目从后向前
        memo = [0] * n
        memo[n-1] = nums[n-1]
        #或者当前房子放弃, 从下一个房子开始考虑
        #或者抢劫当前的房子, 从i+2以后的房子开始考虑
        i = n-2
        while i > = 0:
            if i+2 < n:
                memo[i] = max(memo[i+1],nums[i] + memo[i+2])
            else:
                memo[i] = max(memo[i+1],nums[i])
            i -= 1
        return memo[0]

213 打家劫舍 二

题目变为环形街道
考虑 从0..n-2 和从 1...n-1这两处
定义 rob(nums,start,end)函数
代码1

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])

        def tryrob(nums,start,end):
            preMax = nums[start]
            curMax = max(preMax, nums[start+1])
            # curMax保存当前最大值
            for i in range(start+2, end+1):
                temp = curMax
                curMax = max(nums[i]+preMax,curMax)
                preMax = temp
            return curMax
        return max(tryrob(nums,0,len(nums)-2) , tryrob(nums,1,len(nums)-1))

代码二 实现
这种代码风格更好理解

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])

        def tryrob(nums,s,e):
            
            n = e-s+1
            dp = [0]*n
            dp[0] = nums[s]
            dp[1] = max(nums[s],nums[s+1])

            for i in range(2,n):
                dp[i] = max(dp[i-1], dp[i-2] + nums[s+i]) #要么不要当前这个 ，要么要当前这个
            return dp[n-1]
        return max(tryrob(nums,0,len(nums)-2) , tryrob(nums,1,len(nums)-1))

337 偷东西 三 （二叉树）

递归解法，会超时
递归思路

class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None :
            return 0
        val = 0
        if root.left != None:
            val += self.rob(root.left.left) + self.rob(root.left.right)
            
        if root.right != None:
            val += self.rob(root.right.left) + self.rob(root.right.right)

        return max(val+root.val, self.rob(root.left) + self.rob(root.right))

解法二：可以通过
思路
res[0]表示不取该层，res[1]表示取这层

class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def robSum(root):
            res = [0] * 2
            if root == None:
                return res

            left = [0] * 2
            left = robSum(root.left)

            right = [0] * 2
            right = robSum(root.right)

            # '0'表示不取自身,'1'表示取自身
            res[0] = max(left[0],left[1]) + max(right[0],right[1])
            res[1] = root.val + left[0] + right[1]

            return res
        if root == None:
            return 0 
        value = [0]*2
        value = robsum(root)
        return max(value[0],valu[1])

取消left = [0] *2 的版本：

class Solution:
    """
    @param root: The root of binary tree.
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber3(self, root):
        # write your code here
        
        if root == None:
            return 0
        def robsum(root):
            res = [0]*2
            if root == None:
                return res
            
            left = robsum(root.left)
            right = robsum(root.right)
            
            res[0] = max(left[0],left[1]) + max(right[0], right[1])
            res[1] = root.val + left[0] + right[0]
            
            return res
        value = robsum(root)
        return max(value[0],value[1])

309 买卖股票

买卖股票有是那种状态：buy sell cooldown
可以将sell 和 cooldown合并为一种状态，因为二者都没有持股<不是很懂啊>
思路
代码实现：

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

        sellDp = [0]*len(prices)
        buyDp = [0]*len(prices)

        buyDp[0] = - prices[0]
        sellDp[0] = 0 

        for i in range(1,len(prices)):
            sellDp[i] = max(sellDp[i-1],buyDp[i-1] + prices[i])
            if i >= 2:
                buyDp[i] = max(buyDp[i-1],sellDp[i-2] - prices[i])
            else:
                buyDp[i] = max(buydp[i-1],-prices[i])

        return sellDp[len(prices)-1]

O(1)空间复杂度的写法：

class Solution:
    """
    @param prices: a list of integers
    @return: return a integer
    """
    def maxProfit(self, prices):
        # write your code here
        if prices == None or len(prices) == 0:
            return 0
        
        currBuy = -prices[0]
        currSell = 0  #当天状态
        preSell = 0   #当天前一天状态,第一天设为0
        for i in range(1,len(prices)):
            temp = currSell
            currSell = max(currSell, currBuy + prices[i])
            if i >= 2:
                currBuy = max(currBuy, preSell - prices[i])
            else:
                currBuy = max(currBuy, -prices[i])
            preSell = temp

        return currSell

416 分割等和子集

思路：这个题目其实是0-1背包问题，可考虑用数组中元素填满sum/2的背包，即可求解出该问题.

1.PNG

解法一：动态规划

class Solution:
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        sums = sum(nums)

        if sums%2 == 1:
            return  False

        n = len(nums)
        C = sums//2
        
        memo = [False]*(C+1)
        for i in range(C+1):
            memo[i] = (nums[0] == i)

        for i in range(1,n):
            j = C
            while j >= nums[i]:
                memo[j] = memo[j] or memo[j-nums[i]]
                j -= 1
        return memo[C]

解法二:记忆化搜索(java版本的过了，不知道哪里出错了) python版本调试好了，但是超时了

class Solution:
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        sums = sum(nums)

        if sums % 2 == 1 :
            return False
        memo =[ [-1] * (sums//2 + 1) for i in range(len(nums)]
        

        def tryPar(nums, index, sums):

            if sums ==  0:
                return True
            
            if sums < 0 or index < 0:
                return False  
            
            if memo[index][sums] != -1:
                return memo[index][sums] == 1

            if tryPar(nums,index-1,sums) or tryPar(nums, index-1,sums-nums[index]):
                memo[index][sums] = 1
            else:
                memo[index][sums] = 0
 

            return memo[index][sums] == 1
            
        return tryPar(nums, len(nums)-1, sums//2)

322 Coin change

解法：动态规划
思路：dp[i] 指存要凑够i那么多钱，最小需要的钱数。 外层加层coin循环，指的试是钱币面额越来越多。

class Solution:
    """
    @param coins: a list of integer
    @param amount: a total amount of money amount
    @return: the fewest number of coins that you need to make up
    """
    def coinChange(self, coins, amount):
        # write your code here
        
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        
        for coin in coins:
            for j in range(coin,amount+1):
                dp[j] = min(dp[j], dp[j-coin] + 1)
        
        if dp[amount] == amount + 1:
            return -1
        else:
            return dp[amount]

377 组合总和VI Combination sum IV

思路： 和上边题目很类似：
状态转移方程，好好理解很重要：DP[I] = SUM(DP[I-NUMS[J]] ( I >= NUMS(J))

class Solution:
    """
    @param nums: an integer array and all positive numbers, no duplicates
    @param target: An integer
    @return: An integer
    """
    def backPackVI(self, nums, target):
        # write your code here
        n =len(nums)
        if n == 0 :
            return 0
        
        dp = [0]*(target+1)
        dp[0] = 1 
        
        for i in range(1,target+1):
            for j in range(n):
                if nums[j] <= i:
                    dp[i] = dp[i] + dp[i-nums[j]]
        
        return dp[target]

474 ones and zeroes

思路
dp[i][j][k]表示前i个字符串在0个数不超过j，1个数不超过k时，最多能选的字符串个数
代码实现：

from collections import Counter
class Solution:
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """

        dp = [[0] * (n+1) for i in range(m+1)]  # m行 n列

        for str_ in strs:
            coun = Counter(str_)
            cn0 = coun['0']
            cn1 = coun['1']
            #体会这里从后向前遍历，背包问题空间的优化
            for i in range(m,cn0-1,-1):
                for j in range(n,cn1-1,-1):
                    dp[i][j] = max(dp[i][j], dp[i-cn0][j-cn1] + 1)
        return dp[m][n]

139 word break 单词拆分

思路
用字典里边的词切分 字符串 dp[i]表示字符串长度为i时能否被切分。
代码实现

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """

        # dp[i] 单词在长度为i时候，能否被切分
        dp = [False]*(len(s)+1)

        dp[0] = True
        
        # i从'1'开始就等同于背包中容量从最小开始，j每次从i前一个位置开始
        for i in range(1,len(s)+1):
            for j in range(i-1,-1,-1):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break 
        return dp[len(s)]

494 Target Sum 目标和

思路

1.PNG
代码实现：

class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        sums = 0
        for i in range(len(nums)):
            sums += abs(nums[i])
        
        if (sums+S)%2 == 1 or sums < S:
            return  0
        
        #dp[i] 指和为i的集合个数
        supers = (sums+S)//2
        dp = [0] *(supers+1)

        dp[0] = 1
        for i in range(len(nums)):
            j = supers
            while j-nums[i] >= 0:
                dp[j] += dp[j-nums[i]]
                j -= 1
        return dp[supers]

练习了一下 reduece:

from functools import reduce
class Solution:
    """
    @param nums: the given array
    @param s: the given target
    @return: the number of ways to assign symbols to make sum of integers equal to target S
    """
    def findTargetSumWays(self, nums, s):
        # Write your code here
        
        if nums == [] and s != 0:
            return 0

        sums = reduce(lambda x,y :abs(x)+abs(y),nums)
        supersum = (sums + s)//2

        if (sums+s)%2 == 1 or sums < s:
            return 0

        dp = [0]*(supersum + 1)
        dp[0] = 1

        for item in nums:
            j = supersum
            while j - item >= 0:
                dp[j] += dp[j-item]
                j -= 1
        return dp[supersum]