leetcode 动态规划题目整理

2021/02/18 leetcode 算法
如果文章图片无法显示,可尝试配置host:修复Github图片资源无法显示问题

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

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

公众号:豆仔gogo

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

豆仔gogo

Search

    公众号:豆仔gogo

    豆仔gogo

    Post Directory