def maxProfit(prices): if len(prices) < 2: return 0 min_price = prices[0] max_profit = 0 for price in prices: if price < min_price: min_price = price if price - min_price > max_profit: max_profit = price - min_price return max_profit
def maxProfit2(prices): max_profit = 0 for i in range(1, len(prices)): max_profit += max(0, prices[i] - prices[i - 1]) return max_profit
#O(N) O(1)
def maxProfit3(prices, fee): cash, hold = 0, -prices[0] for i in range(1, len(prices)): cash, hold = max(cash, hold + prices[i] - fee), max(hold, cash - prices[i]) return cash
四、买卖股票 IV
def maxProfit4(prices): total_max_profit = 0 n = len(prices) left_profits = [0] * n min_price = float(‘inf‘) for i in range(n): min_price = min(min_price, prices[i]) total_max_profit = max(total_max_profit, prices[i] - min_price) left_profits[i] = total_max_profit max_profit = 0 max_price = float(‘-inf‘) for i in range(n - 1, 0, -1): max_price = max(max_price, prices[i]) max_profit = max(max_profit, max_price - prices[i]) total_max_profit = max(total_max_profit, max_profit + left_profits[i - 1]) return total_max_profit
#O(n*k) def maxProfit5(prices, k): if len(prices) < 2: return 0 if len(prices) <= k / 2: maxProfit(prices) local = [0] * (k+1) globl = [0] * (k+1) for i in range(1, len(prices)): diff = prices[i] - prices[i - 1] j = k while j > 0: local[j] = max(globl[j - 1], local[j] + diff) globl[j] = max(globl[j], local[j]) j -= 1 return globl[k]
def maxProfit6(prices): if len(prices) < 2: return 0 n = len(prices) sell = [0] * n buy = [0] * n sell[0] = 0; buy[0] = -prices[0] for i in range(1, n): sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]) buy[i] = max(buy[i - 1], (sell[i - 2] if i > 1 else 0) - prices[i]) return sell[-1]
二维动态规划：
def uniquePaths(m, n): aux = [1 for x in range(n)] for i in range(1, m): for j in range(1, n): aux[j] = aux[j]+aux[j-1] return aux[-1]
def uniquePathsWithObstacles(obstacleGrid): M, N = len(obstacleGrid), len(obstacleGrid[0]) dp = [1] + [0] * (N-1) for i in range(M): for j in range(N): if obstacleGrid[i][j] == 1: dp[j] = 0 elif j > 0: dp[j] += dp[j-1] return dp[N-1]
def movingBoard(board): result = board m = len(board) n = len(board[0]) for i in range(1, m): for j in range (0, n): result[i][j] = max(0 if j == 0 else result[i-1][j-1], result[i-1][j], 0 if j == n-1 else result[i-1][j+1] ) + board[i][j] return max(result[-1])
空间优化：
def movingBoard2(board): result = board[0] m = len(board) n = len(board[0]) for i in range(1, m): for j in range (0, n): result[j] = max(0 if j == 0 else result[j-1], result[j], 0 if j == n-1 else result[j+1] ) + board[j] return max(result)
def maximalSquare(matrix): if matrix == []: return 0 m, n = len(matrix), len(matrix[0]) dp = [[0] * n for x in range(m)] ans = 0 for x in range(m): for y in range(n): dp[x][y] = int(matrix[x][y]) if x and y and dp[x][y]: dp[x][y] = min(dp[x - 1][y - 1], dp[x][y - 1], dp[x - 1][y]) + 1 ans = max(ans, dp[x][y]) return ans * ans
空间优化：
def maximalSquare(matrix): if matrix == []: return 0 m, n = len(matrix), len(matrix[0]) dp = matrix[0] ans = 0 for x in range(0, m): for y in range(0, n): dp[y] = int(matrix[x][y]) if matrix[x][y]: dp[y] = min(dp[y - 1], dp[y - 1], dp[y]) + 1 ans = max(ans, dp[y]) return ans * ans
原文：https://www.cnblogs.com/oldby/p/12842073.html