leetcode-动态规划题目整理

2021/02/18 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。

题解资料:

子串和子序列的定义

image

题解思路:

创建二维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]);
}

image-20210218171441430

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]
}

附录:题目汇总

1、线性 DP

2、区间 DP

516. 最长回文子序列

730. 统计不同回文子字符串

1039. 多边形三角剖分的最低得分

664. 奇怪的打印机

312. 戳气球

3、背包 DP

416. 分割等和子集 (01背包-要求恰好取到背包容量)

494. 目标和 (01背包-求方案数)

322. 零钱兑换 (完全背包)

518. 零钱兑换 II (完全背包-求方案数)

474. 一和零 (二维费用背包)

4、树形 DP

124. 二叉树中的最大路径和

1245. 树的直径 (邻接表上的树形DP)

543. 二叉树的直径

333. 最大 BST 子树

337. 打家劫舍 III

5、状态压缩 DP

464. 我能赢吗

526. 优美的排列

935. 骑士拨号器

1349. 参加考试的最大学生数

6、数位 DP

233. 数字 1 的个数

902. 最大为 N 的数字组合

1015. 可被 K 整除的最小整数

7、计数型 DP

计数型DP都可以以组合数学的方法写出组合数,然后dp求组合数

62. 不同路径

63. 不同路径 II

96. 不同的二叉搜索树 (卡特兰数)

1259. 不相交的握手 (卢卡斯定理求大组合数模质数)

8、递推型 DP

所有线性递推关系都可以用矩阵快速幂做,可以O(logN),最典型是斐波那契数列

70. 爬楼梯

509. 斐波那契数

935. 骑士拨号器

957. N 天后的牢房

1137. 第 N 个泰波那契数

9、概率型 DP

求概率,求数学期望

808. 分汤

837. 新21点

10、博弈型 DP

策梅洛定理,SG 定理,minimax

11、记忆化搜索

本质是 dfs + 记忆化,用在状态的转移方向不确定的情况

329. 矩阵中的最长递增路径

576. 出界的路径数


公众号:豆仔gogo

golang、算法、后端知识、面试手册

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory