動態(tài)規(guī)劃

三要素:

狀態(tài)
狀態(tài)轉(zhuǎn)移方程
空間換時間:保存每一步的遞推結(jié)果

1. leetcode 300.最長遞增子串 (LIS)

給定一個數(shù)列习瑰，長度為N悔橄，
求這個數(shù)列的最長上升（遞增）子數(shù)列（LIS）的長度.
以1 7 2 8 3 4為例日矫。
這個數(shù)列的最長遞增子數(shù)列是 1 2 3 4斋攀，長度為4到腥；
次長的長度為3， 包括 1 7 8; 1 2 3 等.

什么是狀態(tài)轉(zhuǎn)移方程萌业？
上述狀態(tài)定義好之后坷襟，狀態(tài)和狀態(tài)之間的關(guān)系式，就叫做狀態(tài)轉(zhuǎn)移方程生年。
對于LIS這個問題婴程，狀態(tài)轉(zhuǎn)移方程為：

F1 = 1
Fn =max(Fi +1 | Ak > Ai, i 屬于(1 .. k-1)) (k>1)

用文字解釋一下是：
以第k項(xiàng)結(jié)尾的LIS的長度是：保證第i項(xiàng)比第k項(xiàng)小的情況下，以第i項(xiàng)結(jié)尾的LIS長度加一的最大值抱婉，取遍i的所有值（i小于k）档叔。

#代碼桌粉，開一個同樣空間的F列表來保存每一個子狀態(tài)當(dāng)前的最大長度
#對于每一個當(dāng)前位置i，要比較小于i的所有位置F上的值
#復(fù)雜度 O(n^2)

def lis_dp(nums):
    F = [1] * len(nums)
    for i in range(1,len(nums)):
        tmp_max = 1
        for j in range(i):
            if nums[i] > nums[j]:
                if F[j] + 1 > tmp_max:
                    tmp_max = F[j] + 1
        F[i] = tmp_max
    print(F)
    return max(F)

2. leetcode 70. 爬樓梯

# 爬樓梯問題衙四，一個人每次可以爬一階或兩階樓梯铃肯，問爬上N階樓梯有多少種爬法
# 問題可以轉(zhuǎn)化為子問題N-1階樓梯的爬法與N-2階樓梯的爬法之和（分別再爬一階或兩階）
狀態(tài)轉(zhuǎn)移方程:
dp(i) = dp(i-1) + dp(i-2)
# N = 1 時候有一種爬法
# N = 2 時候有兩種爬法（2或1+1）

def palouti(num):
    dp = [0] * num 
    dp[0] = 1
    dp[1] = 2
    for i in range(2,num):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[num - 1]

# 和斐波那契數(shù)列很像，為了減少計算復(fù)雜度届搁，使用DP的思想缘薛，拿一個數(shù)組保存之前子問題的計算結(jié)果

3. leetcode 53 最大子數(shù)組

Maximum Subarray

# 給定一個整數(shù)數(shù)組，找到一個具有最大和的子數(shù)組卡睦，返回其最大和宴胧。
# 給出數(shù)組[?2,2,?3,4,?1,2,1,?5,3]，符合要求的子數(shù)組為[4,?1,2,1]表锻，其最大和為6

def maxSubArray(nums):
    tmp_max = nums[0] # tmp_max 全局到當(dāng)前位置的最大保存值
    cur_max = nums[0] # 當(dāng)前連續(xù)序列的最大值
    for i in range(1,len(nums)):
        cur_max = max(cur_max + nums[i],nums[i]) # 判斷當(dāng)前的數(shù)組元素是否要替換之前連續(xù)的數(shù)組元素
        #比如下面開頭的[-4,5]恕齐，到5當(dāng)前最大[5]為5，大于[-4,5]的1瞬逊，因此新的最大子數(shù)組一定以5開頭
        if cur_max > tmp_max:
            tmp_max  = cur_max
    return tmp_max

if __name__ == '__main__':
    a = [-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-1000]
    print(maxSubArray(a))

4.最大子數(shù)組 II -lintcode42

# 給定一個整數(shù)數(shù)組显歧，找出兩個 不重疊 子數(shù)組使得它們的和最大。
每個子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的确镊。
返回最大的和士骤。
# 給出數(shù)組 [1, 3, -1, 2, -1, 2]
這兩個子數(shù)組分別為 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它們的最大和都是 7

做法1：
遍歷該數(shù)組蕾域，對于每個分割點(diǎn)拷肌，用上面最大子數(shù)組的方法分別對左邊合右邊求最大子數(shù)組的和，取最大的和旨巷，復(fù)雜度O(n^2)

做法2: 
DP方法巨缘，提前記錄好每個位置上之前的數(shù)組的最大子數(shù)組之和
把該數(shù)組從左到右遍歷，記錄每一個位置上之前數(shù)組的最大子數(shù)組之和
再從右往左遍歷采呐，同樣記錄
之后對于每一個i到len(nums)-1的index若锁，計算從左到右和從右到左對應(yīng)位置最大子數(shù)組之和，最大的為結(jié)果斧吐，復(fù)雜度O(n)
class Solution:
    """
    @param: nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    """
    

    def subArray(self,nums):
        F = [0] * len(nums)
        tmp_max = nums[0]
        cur_max = nums[0]
        F[0] = nums[0]
        for i in range(1,len(nums)):
            cur_max = max(cur_max + nums[i],nums[i])
            tmp_max = max(tmp_max,cur_max)
            F[i] = tmp_max
        return F


    def maxTwoSubArrays(self, nums):
        all_max = nums[0] + nums[1]
        F = self.subArray(nums) # 從左到右
        nums.reverse()
        F1 = self.subArray(nums) # 從右到左
        
        for i in range(1,len(nums)-1):
            tmp_max = F[i] + F1[len(nums)-2-i] # 這里下標(biāo)需要注意
            all_max = max(tmp_max,all_max)
        
        return all_max

leetcode 62 Unique Paths

在一個M * N的矩陣中又固，start為左下角(1,1)點(diǎn)，end為右上角(m,n)煤率，只能向上或者向右走口予，有多少種獨(dú)立的走法?

DFS法:
樹結(jié)構(gòu)走，每次走[0,1]代表上和右涕侈，dfs結(jié)束條件為 up + right = m + n -2 (注意是從1,1開始所以要-2）
dfs返回條件是up >=m or n >= n
該種方法樹剪枝的效率一般沪停，leetcode上會超時，但是方便打印所有走的路線。

class Solution(object):
    def uniquePaths(self, m, n):
        
        def dfs(up,right,m,n,path,nums,nb):
            if up >= m or right >= n:
                return 
            if len(path) ==  m + n - 2:
                nb.append(path) 
                return 
            for i in nums:
                if i == 0:
                    dfs(up + 1,right,m,n,path + [0],nums,nb)
                if i == 1:
                    dfs(up, right + 1,m,n,path+[1],nums,nb)
        
        nums = [0,1]
        path,up,right,nb = [],0,0,[]
        dfs(up,right,m,n,path,nums,nb)
        return len(nb)

DP法
狀態(tài)轉(zhuǎn)移方程:
dp(m,n) = dp(m-1,n) + dp(m,n-1)
走到當(dāng)前位置的走法相當(dāng)于走到左邊的走法加上走到右邊的走法數(shù)量木张。

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1 for x in range(n)] for x in range(m)]
        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]

leetcode 63 Unique Path2

從矩陣左下角走到右上角（或叫左上角走到右下角）的獨(dú)立path個數(shù)众辨，只能走up或者right，一次走一步舷礼，矩陣?yán)锸怯衎lock的鹃彻，block表示為1，通路表示為0

如
0 0 0 
0 1 0
0 0 0
從左下走到右上妻献，由于正中間有一個block蛛株，因此只有兩條path
即 [up,up,right,right] 或者 [right,right,up,up]

狀態(tài)轉(zhuǎn)移方程

兩個一樣大小的矩陣M和dp，M保存矩陣中碰到阻礙的情況（1是阻礙）
dp中保存矩陣中起點(diǎn)到當(dāng)前位置的不同path數(shù)量
1. 初始dp[0][0] = 1 - M[0][0] 育拨，因?yàn)镸=0是暢通谨履，M=1是阻礙
2. 當(dāng)i == 0 or j ==0 時: #兩條邊
     if M[i][0] == 1:
        dp[i][0] = 0
     else:
         dp[i][0] = dp[i-1][0] 
對dp[0][j]同理
3. 當(dāng)i >= 1 and j >= 1時:
  if M[i][j] == 1:
      dp[i][j] = 0
  elif M[i][j] == 0:
      dp[i][j] = dp[i-1][j] + dp[i][j-1]

最終代碼：
這種解法可讀性較強(qiáng)，空間復(fù)雜度O(m*n), leetcode discuss上也有空間復(fù)雜度O(n)和in-place的熬丧，可見https://discuss.leetcode.com/topic/19795/python-different-solutions-o-m-n-o-n-in-place （其中O（m*n）和這個解法一模一樣笋粟，代碼更trick一些）

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

        for i in range(1,n): # left edge
            if obstacleGrid[0][i] == 1:
                dp[0][i] = 0
            else:
                dp[0][i] = dp[0][i-1]

        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

leetcode 64. Minimum 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.

Example 1:
[[1,3,1],
 [1,5,1],
 [4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

1. DFS暴力解法害捕，遍歷全部路徑，記錄sum最短的那條闷畸，見函數(shù)minPathSum-dfs
2. DP解法尝盼，見函數(shù)dp

狀態(tài)轉(zhuǎn)移方程：
if i == 0 or j == 0 (在兩條邊): 
    dp[i][0] = dp[i-1][0] + M[i][0]
    dp[0][j] = dp[0][j-1] + M[0][j]
else:
  dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + M[i][j] # 如果是sum最大路徑，這里min換成max就可以

DFS在leetcode上會超時不能AC佑菩，一部分tests沒法通過

#coding=utf-8
class Solution(object):
    def minPathSum(self, grid):
        path = [grid[0][0]]
        res = []
        self.res_final = []
        height = len(grid)
        length = len(grid[0])
        self.m = height 
        self.n = length
        self.max_tmp = 1e10
        self.dfs(grid,0,0,path,res)
        return sum(self.res_final)
    def dfs(self,grid,height,length,path,res):
    
        if len(path) == self.m + self.n - 1:
            # print(path)
            if sum(path) < self.max_tmp:
                self.max_tmp = sum(path)
                self.res_final = path
        for i in range(2):
            if i == 0 : # means go right
                if length + 1 > self.m - 1:
                    continue
                self.dfs(grid,height,length + 1,path + [grid[length+1][height]],res)
                
            if i == 1 : # means go down
                if height + 1 > self.n - 1:
                    continue
                self.dfs(grid,height + 1,length,path + [grid[length][height + 1]],res)
               

DP法

    def dp(self,grid):
        height = len(grid)
        length = len(grid[0])
        dp = [[0 for i in range(length)] for j in range(height)]
        dp[0][0] = grid[0][0]
        
        for i in range(1,height):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1,length):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        
        for i in range(1,height):
            for j in range(1,length):
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j] # dp[1][1] = dp[1][0] + dp[0][1]
        
        return dp[height-1][length-1]

if __name__ == '__main__':
    Solution = Solution()
    grid = [[1,3,1,1],[4,2,1,1],[4,2,4,1]]#
    # grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(Solution.minPathSum(grid))
    print(Solution.dp(grid))

leetcode 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).
給定一個三角形东涡，從頂往下走，每個點(diǎn)只能走下面的左右相鄰的兩點(diǎn)倘待，求和為最小的路徑的和的值

一般來說，求最后的值不用打印路徑的都可以用DP完成组贺，需要打印路徑的可以用DFS完成凸舵。
顯然狀態(tài)轉(zhuǎn)移方程為下：

T: 三角形的值數(shù)組，dp當(dāng)前和最小路徑的數(shù)組失尖，T和dp大小完全一致啊奄。
1. dp[0][0] = T[0][0]
2. for i in range(1,len(dp)): # 從第二行開始
      對于每行第一個元素：dp[i][j] = dp[i-1][j] + T[i][j] （三角形，只能接收上一行最左元素）
      對于每行最后一個元素：dp[i][j] = dp[i-1][j-1] + T[i][j] （三角形掀潮，只能接收上一行最右元素）
      對于每行中間的元素：dp[i][j] = min(dp[i-1][j-1] ,dp[i-1][j]) + T[i][j]
  

code菇夸，空間O(m*n)

class Solution:
    
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = [[i for i in j] for j in triangle]

        dp[0][0] = triangle[0][0]
        for i in range(1,len(triangle)):
            for j in range(len(triangle[i])):
                if j == 0 :
                    dp[i][j] = dp[i-1][j] + triangle[i][j]
                    print(dp[i][j])
                elif j == len(triangle[i]) - 1:
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1] ,dp[i-1][j]) + triangle[i][j]
        
        return min(dp[len(dp)-1])