leetcode-动态规划题目整理

前言：股票的最大利润、最长公共子序列

1、股票的最大利润

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float("+inf")
        res = 0
        for price in prices:
            low = min(low, price)
            res = max(res, price-low)
        return res

2、最长公共子序列

原题地址：1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，
但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

题解资料：

原博主视频：https://www.bilibili.com/video/BV14A411v7mP?zw
自制视频：
调试工具：https://alchemist-al.com/algorithms/longest-common-subsequence

子串和子序列的定义

题解思路：

创建二维dp表，核心dp伪代码

if (a === b) { // 相等，取左上角+1
  table[row][col] = table[row - 1][col - 1] + 1;
} else {// 不相等，取上，左中的最大值
  table[row][col] = Math.max(table[row][col - 1], table[row - 1][col]);
}

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 建立二维数组
        # 使用这种二维数组初始化坑死我了
        # arr_in = [0] * (len(text1) + 1)
        # arr = [arr_in for i in range(len(text2) + 1)]
        arr = [[0] * (len(text1) + 1) for i in range(len(text2) + 1)]
        # 遍历二维数组
        for i in range(1, len(text2) + 1):
            for j in range(1, len(text1) + 1):
                if text1[j - 1] == text2[i - 1]:
                    arr[i][j] = arr[i - 1][j - 1] + 1
                else:
                    arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])
        # 返回最终值
        return arr[-1][-1]

func longestCommonSubsequence(text1 string, text2 string) int {
	row := len(text2) + 1
	col := len(text1) + 1

	arr := make([][]int, row)
	for i := range arr {
		arr[i] = make([]int, col)
	}

	for i := 1; i < row; i++ {
		for j := 1; j < col; j++ {
			if text2[i-1] == text1[j-1] {
				arr[i][j] = arr[i-1][j-1] +1
			} else {
				arr[i][j] = int(math.Max(float64(arr[i][j-1]), float64(arr[i-1][j])))
			}
		}
	}
	return arr[row-1][col-1]
}