70-爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。

class Solution:
    def climbStairs(self, n: int) -> int:
        # 動(dòng)態(tài)規(guī)劃
        if n <= 2:
            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]

121-買賣股票的最佳時(shí)機(jī)

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。

• 方法1：貪心逐步計(jì)算出最小買入價(jià)格，以及最大賣出利潤

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = float('inf')     # 極大值
        maxProfit = 0               # 初始最大利潤為0
        for price in prices:
            minPrice = min(minPrice, price)
            maxProfit = max(maxProfit, price-minPrice)
        return maxProfit

• 方法2：動(dòng)態(tài)規(guī)劃

(1)只有賣和不賣兩種選擇
選擇買：min_price = min(min_price, prices[i])
選擇賣：dp[i] = prices[i] - min_price
選擇不賣：dp[i] = dp[i-1]
動(dòng)態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1], prices[i]-min_price)
(2)初始條件：dp[0] = 0表示

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        dp = [0]*len(prices)
        dp[0] = 0
        min_price = prices[0]
        for i in range(1, len(prices)):
            min_price = min(min_price, prices[i])
            dp[i] = max(dp[i-1], prices[i]-min_price)
            print(dp[i])
        return dp[-1]

62-不同路徑

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。
問總共有多少條不同的路徑？

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for j in range(m)]
        # 第一種寫法
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                # 左邊有有效值
                if i-1 >= 0 and i-1 < m:
                    dp[i][j] = dp[i][j] + dp[i-1][j]
                # 右邊有有效值
                if j-1 >= 0 and j-1 < n:
                    dp[i][j] = dp[i][j] + dp[i][j-1]
        return dp[m-1][n-1]

        # 第二種寫法
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 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]

        # 動(dòng)態(tài)規(guī)劃優(yōu)化
        dp = [0]*n
        for i in range(n):
            dp[i] = 1
        for i in range(1, m):
            dp[0] = 1
            for j in range(1, n):
                dp[j] = dp[j-1] + dp[j]
                
        return dp[n-1]

# 遞歸寫法
# 1 遞歸關(guān)系式:dfs(i,j) = dfs(i-1, j) + dfs(i, j-1)
# 2 找出初始值:如果i或者j有一個(gè)為0,那么不能使用關(guān)系式
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        arr = [[0 for i in range(n)] for j in range(m)]
        return self.dfs(m-1, n-1, arr)
    
    def dfs(self, i, j, arr):
        if i == 0 or j == 0:
            return 1
        if arr[i][j] != 0:
            return arr[i][j]
        arr[i][j] = self.dfs(i-1, j, arr) + self.dfs(i, j-1, arr)
        return arr[i][j]

64-最小路徑之和

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因?yàn)槁窂?1→3→1→1→1 的總和最小。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for j in range(n)] for i in range(m)]

        dp[0][0] = grid[0][0]
        # 初始化最左邊的列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        # 初始化最上面的行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]

        # 計(jì)算剩余的值
        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])
        # print(dp)        
        return dp[m-1][n-1]

72-編輯距離

輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 動(dòng)態(tài)規(guī)劃關(guān)系式
        # 插入：dp[i][j] = dp[i][j-1] + 1
        # 刪除：dp[i][j] = dp[i-1][j] + 1
        # 替換：dp[i][j] = dp[i-1][j-1] + 1
        # 關(guān)系式：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
        m = len(word1)
        n = len(word2)
        dp = [[0 for j in range(n+1)] for i in range(m+1)]
        # dp[0][0...n] 初始化
        for i in range(1,n+1):
            dp[0][i] = dp[0][i-1] + 1
        for j in range(1,m+1):
            dp[j][0] = dp[j-1][0] + 1

        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
        return dp[m][n]

        # 動(dòng)態(tài)規(guī)劃優(yōu)化
        m = len(word1)
        n = len(word2)
        dp = [0]*(n+1)

        # 初始化dp[0...n]的值
        for i in range(n+1):
            dp[i] = i
        
        for i in range(1, m+1):
            tmp = dp[0]
            dp[0] = i
            for j in range(1, n+1):
                pre = tmp
                tmp = dp[j]
                if word1[i-1] == word2[j-1]:
                    dp[j] = pre
                else:
                    dp[j] = min(min(dp[j-1], pre), dp[j]) + 1
        return dp[n]

53-最大子序和

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

思路（正數(shù)實(shí)現(xiàn)增加）：
若前一個(gè)元素大于0，則將其加到當(dāng)前元素上

狀態(tài)轉(zhuǎn)移方程：f(i) = max{f(i-1) + nums[i], nums[i]}

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(1, n):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]    # 滾動(dòng)數(shù)組
        return max(nums)

• 1 定義數(shù)組的含義
  dp[i]:以nums[i]結(jié)尾的子序的最大和
  max = max(dp[0], dp[1], ... dp[n-1])
• 2 找到數(shù)組元素之間的關(guān)系式
  對(duì)于每一個(gè)房間,小偷可以選擇偷或者不偷
  不偷: dp[i] = dp[i-1]
  偷: dp[i] = dp[i-1] + nums[i]
  關(guān)系式為:dp[i] = max(dp[i-1], dp[i-1]+nums[i])
• 3 數(shù)組元素的初始值
  dp[0] = nums[0]

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if nums == None or len(nums) == 0:
            return 0
        length = len(nums)
        dp = [0]*(length)
        dp[0] = nums[0]
        resMax = dp[0]
        for i in range(1, length):
            dp[i] = max(nums[i], dp[i-1] + nums[i])
            if dp[i] > resMax:
                resMax = dp[i]
        return resMax

198-打家劫舍

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。

• 1 定義數(shù)組的含義:
  dp[i]當(dāng)小偷到達(dá)i號(hào)房屋時(shí),最高可以盜竊的金額是dp[i]
• 2 數(shù)組元素之間的關(guān)系:
  小偷只有兩種選擇,偷還是不偷
  不偷:dp[i] = dp[i-1]
  偷: dp[i] = dp[i-2] + nums[i] # 相鄰房間不可以偷竊
  關(guān)系式:dp[i] = max(dp[i-1], dp[i-2]+nums[i])
• 3 找出初始值
  當(dāng)只有一個(gè)房間,必須偷竊:dp[0] = nums[0]
  當(dāng)有兩個(gè)房間時(shí),偷竊較多金額的房間:dp[1] = max(nums[0], nums[1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0 or nums == None:
            return 0
        length = len(nums)
        dp = [0]*(length)
        dp[0] = nums[0]
        # 數(shù)組邊界判定,防止越界
        if len(nums) < 2:
            return nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, length):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return dp[length-1]

322-兌換硬幣

輸入：coins = [1, 2, 5], amount = 11
輸出：3 (最少硬幣數(shù)量)
解釋：11 = 5 + 5 + 1

• 1 定義數(shù)組的含義
  dp[i]:湊成總金額n所需的最少硬幣數(shù)量,dp[amount]就是我們想要的答案

• 2 找出數(shù)組元素之間的關(guān)系
  對(duì)于每一枚硬幣coins[j]我們只有兩種選擇,選或者不選
  如果選擇:dp[i] = dp[i-coins[j]] + 1
  如果不選擇:dp[i] = dp[i]
  所以公式為:dp[i] = min(dp[i], dp[i-coins[j]] + 1])

• 3 找到初始值
  當(dāng)i=0時(shí),dp[0] = 0
  為了防止取最小值時(shí)dp[i]被覆蓋,因此給dp[i]賦予一個(gè)盡量大的值

• 動(dòng)態(tài)規(guī)劃

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0

        for i in range(1,amount+1):
            for j in range(len(coins)):
                # 滿足兌換的條件
                if coins[j] <= i:
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1)
        if dp[amount] > amount:
            return -1
        else:
            return dp[amount]

120-三角形最小路徑和

輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11

將上面的數(shù)組進(jìn)行轉(zhuǎn)化：
triangle =
[[2],
[3,4],
[6,5,7],
[4,1,8,3]]
需要注意邊界條件！

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 1:
            return triangle[0][0]

        n = len(triangle)
        dp = [[0]*n for _ in range(n)]
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            # 最左側(cè)的列只能由正上方元素計(jì)算
            dp[i][0] = dp[i-1][0] + triangle[i][0]
            for j in range(1, i):
                minNum = min(dp[i-1][j-1], dp[i-1][j])
                dp[i][j] = triangle[i][j] + minNum
            # 最右側(cè)的列只能由左上方元素計(jì)算
            dp[i][i] = dp[i-1][i-1] + triangle[i][i]
        print(dp)
        return min(dp[n-1])

10-正則表達(dá)式匹配

給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配。

• '.' 匹配任意單個(gè)字符
• '*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
  所謂匹配，是要涵蓋 整個(gè) 字符串 s的，而不是部分字符串。

輸入：s = "ab" p = "."
輸出：true
解釋："." 表示可匹配零個(gè)或多個(gè)（'*'）任意字符（'.'）。

public boolean isMatch1(String s, String p){ 
  if(s == null || p == null) return false; 
  int len_s = s.length(); 
  int len_p = p.length(); 
  //存放狀態(tài)，默認(rèn)初始值都是 false。 
  boolean[][]dp = new boolean[len_s+1][len_p+1]; 
  //初始化 
  dp[0][0] = true; 
  for(int j = 1; j <= len_p; j++){ 
    if(p.charAt(j-1) == '*') 
    dp[0][j] = dp[0][j-2]; } 
  for(int i = 1; i <= len_s; i++){ 
    for(int j = 1; j <= len_p; j++){ 
    //如果不為‘*’且匹配 
      if(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1)) 
        dp[i][j] = dp[i-1][j-1]; 
        //如果是 * 
      else if(p.charAt(j-1)=='*'){ 
          //如果p[j]前面的字符p[j-1]與s[i]字符不匹配，則匹配0個(gè) 
        if(j!=1&&p.charAt(j-2)!='.'&&p.charAt(j-2)!=s.charAt(i-1)){ 
          dp[i][j] = dp[i][j-2]; }
      else{ 
            //否則有三種情況： //匹配0個(gè)，匹配1個(gè)，匹配多個(gè) 
          dp[i][j] = dp[i][j-2] || dp[i][j-1]||dp[i-1][j]; 
        } 
      } 
    } 
  } 
  return dp[len_s][len_p]; }
}