LiSheng's blog
lisheng
2024-09-10
目录

动态规划

# 动态规划

# 0-1背包问题

# 分割等和子集 (opens new window)

给你一个 **只包含正整数 **的 **非空 **数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

func canPartition(nums []int) bool {
    if len(nums) == 1 {
        return false
    }

    sum, max := 0, 0
    for _, v := range nums {
        sum += v
        if max < v {
            max = v
        }
    }

    if sum%2 != 0 {
        return false
    }

    target := sum/2
    if max > target {
        return false
    }

    dp := make([]bool, target+1)
    dp[0] = true
    //物品不可重用，物品放外层循环
    for i:=0; i<len(nums); i++ {
        for j:= target; j >= nums[i]; j-- {
            dp[j] = dp[j] || dp[j-nums[i]] //此处dp大数需要依赖比自己小的数，所以只能递减j--, j++的话dp中数据就会被覆盖还在使用
        }
    }
    return dp[target]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 最后一块石头的重量 II (opens new window)

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，**最多只会剩下一块 **石头。返回此石头 **最小的可能重量 **。如果没有石头剩下，就返回 0。

func lastStoneWeightII(stones []int) int {
    total := 0
    for _, n := range stones {
        total += n
    }

    half := total/2

    dp := make([]bool, half + 1)
    dp[0] = true
    tmp := make([]bool, len(dp))
    for i:=0; i<len(stones); i++ {
        copy(tmp, dp)
        for j:=stones[i]; j<= half; j++ {
            if tmp[j-stones[i]] == true {
                dp[j] = true
            }
        }
    }

    left := half
    for dp[left] == false {
        left--
    }
    return total-2*left
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 目标和 (opens new window)

给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if abs(target) > sum {
		return 0
	}
	if (sum+target)%2 == 1 {
		return 0
	}
	
	bag := (sum + target) / 2  	 	// 计算背包大小
	dp := make([]int, bag+1)   		// 定义dp数组
	dp[0] = 1						// 初始化
	for i := 0; i < len(nums); i++ {   // 遍历顺序
		for j := bag; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]]    	//推导公式
		}
	}
	return dp[bag]
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 一和零 (opens new window)- 两个背包

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

func findMaxForm(strs []string, m int, n int) int {
    //背包有两个维度要求，所以dp设置为二维数组
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = 0
    }

    //物品只能用一次，放最外成遍历
    for _, str := range strs {
        zero_count := strings.Count(str, "0")
        one_count := strings.Count(str, "1")

        //需要同时满足两个背包达到指定容量，zero_count, one_count
        for i:=m; i>=zero_count; i-- {
            for j:=n; j>=one_count; j-- {
                dp[i][j] = max(dp[i][j], dp[i-zero_count][j-one_count] + 1)
                // 01背包，放或者不放, 把放入该str情况下能到达的dp位置置为1，方便后续str接着放
                // 最后取出dp[m][n]位置的值
            }
        }
    }

    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 完全背包问题

# 518.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。 假设每一种面额的硬币有无限个 。 示例 1: 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    dp[0] = 0
    for i:=1; i<=amount; i++ {
        dp[i] = math.MaxInt32
        for _, val := range coins {
            if i-val >=0 {
                dp[i] = min(dp[i], dp[i-val]+1)
            }
        }
    }
    if dp[amount] == math.MaxInt32 {
        dp[amount] = -1
    }
    return dp[amount]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 518.零钱兑换II

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for i:=0; i<len(coins); i++ {
		for j:=coins[i]; j<=amount; j++ {
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}
1
2
3
4
5
6
7
8
9
10

# 279.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。返回和为 n 的完全平方数的 最少数量

# 139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 **注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 。示例 1： 输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s)+1)
    dp[0] = true

    for i:=1; i<=len(s); i++ {
        for _, str := range wordDict {
            if dp[i-1] == true && i+len(str)-1<=len(s) && str == s[i-1:i+len(str)-1] {
                dp[i+len(str)-1] = true
            }
        }
    }
    return dp[len(s)]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    vector<int> dp(n + 1, false);
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        for (auto word : wordDict) {
            if (dp[i] && word.size() + i - 1 < n &&
                word == s.substr(i, word.size())) {
                dp[i + word.size()] = true;
            }
        }
    }
    if (dp[n]) {
        return true;
    }
    return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 打家劫舍

# 198.打家劫舍-数组

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你** 不触动警报装置的情况下 **，一夜之内能够偷窃到的最高金额

func rob(nums []int) int {
    switch len(nums){
        case 0: return 0
        case 1: return nums[0]
    }
    n := len(nums)
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = nums[0]
    for i:=2; i<=n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    }
    return dp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 213.打家劫舍 数组环

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

func robHelper(nums []int) int {
    switch len(nums){
        case 0: return 0
        case 1: return nums[0]
    }
    n := len(nums)
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = nums[0]
    for i:=2; i<=n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    }
    return dp[n]
}

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    return max(robHelper(nums[:len(nums)-1]), robHelper(nums[1:]))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 337.打家劫舍 树

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额

分析： 两种选择，（1）选择偷父节点且不偷子节点，（2）选择偷子节点不偷父节点 两种方案都需要依次返回到最终的根节点才能得出结论，所以需要个数组保存结果

func rob(root *TreeNode) int {
    res := robTree(root)
    return max(res[0], res[1])
}

func robTree(node *TreeNode) []int {
    if node == nil {
        return []int{0, 0}
    }

    left := robTree(node.Left)
    right := robTree(node.Right)

    robCur := left[0] + right[0] + node.Val
    NotRobCur := max(left[0], left[1]) + max(right[0], right[1])

    return []int{NotRobCur, robCur}
}
//树形dp, 对于每个节点有两个状态，dp[0], dp[1] 分别表示不rob当前节点，和rob当前节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 买卖股

# 121.限定只买一次

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。计算你所能获取的最大利润。

# 122.不限买卖次数

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

func maxProfit(prices []int) int {
    n, res := len(prices), 0
    dp := make([]int, n)
    dp[0] = prices[0]
    for i:=1; i<n; i++ {
        dp[i] = min(dp[i-1], prices[i])
        res = max(res, prices[i] - dp[i])
    }
    return res
}
1
2
3
4
5
6
7
8
9
10

# 123.限制买两次

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易

func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    for i := 0; i < len(prices); i++ {
        dp[i] = make([]int, 5)
    }
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    dp[0][2] = 0
    dp[0][3] = -prices[0]
    dp[0][4] = 0
    for i := 1; i < len(prices); i++ {
        dp[i][0] = 0   // 表示初始化资产
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) // 奇数表示买入后资产，偶数表示卖出后资产
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]) 
        dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
        dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
    }
    return dp[len(prices)-1][4]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 188.限制买k次

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 K笔 交易

func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    k := 2
    for i:=0; i<len(prices); i++ {
        dp[i] = make([]int, 2*k+1)
    }

    for i:=0; i<k; i++ {
        dp[0][2*i] = 0
        dp[0][2*i+1] = -prices[0]
    }
    
    for i:=1; i<len(prices); i++ {
        dp[i][0] = 0

        // 奇数表示买入后资产，
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
        for j:=1; j<k; j++ {
            //这里的每次的+prince[i]都是在一次受益。dp[][2*i]就代表了当允许最多i次交易是能收获的最大值，最多受益也就是每次涨能踩中受益
            dp[i][2*j] = max(dp[i-1][2*j], dp[i-1][2*j-1] + prices[i])
            dp[i][2*j+1] = max(dp[i-1][2*j+1], dp[i-1][2*j] - prices[i])
        }
        dp[i][2*k] = max(dp[i-1][2*k], dp[i-1][2*k-1] + prices[i])
    }
    return dp[len(prices)-1][2*k]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maxProfit(k int, prices []int) int {
    n := len(prices)
    buy := make([]int, k+1)
    sell := make([]int, k+1)
    for i:=0; i<=k; i++ {
        buy[i] = math.MinInt
    }

    for i:=1; i<=n; i++ {
        for j:=1; j<=k; j++ {
            buy[j] = max(buy[j], sell[j-1] - prices[i-1])
            sell[j] = max(sell[j], buy[j] + prices[i-1])
        }
    }
    return sell[k]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 309.含冷冻期

# 714.含手续费

# 子序列问题

# 最长递增子序列 (opens new window)

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

对于 j < i, 且nums[j] < nums[i]，则以【0，i】区间的递增子序列就包含了nums[j], 长度加一 dp[i] = max(dp[i], dp[j] + 1

func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = 1
    res := 1
    n := len(nums)
    for i:=1; i<n ; i++ {
        dp[i] = 1
        for j:=0; j<i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            } 
        }
        res = max(res, dp[i])
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 最长连续递增子序列 (opens new window)

给定一个未经排序的整数数组，找到最长且** 连续递增的子序列**，并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

func findLengthOfLCIS(nums []int) int {
    res := 1
    tmp := 1
    for i:=1; i<len(nums); i++ {
        if nums[i] > nums[i-1] {
            tmp++
            res = max(res, tmp)
        } else {
            tmp = 1
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 最长重复子数组 (opens new window)

给两个整数数组 nums1 和 nums2 ，返回 _两个数组中 公共的 、长度最长的子数组的长度 _。

func findLength(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    res := 0
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
    }

    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            res = max(res, dp[i][j])
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 最长公共子序列 (opens new window)

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列_ _是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
    }
    for i, c1 := range text1 {
        for j, c2 := range text2 {
            if c1 == c2 {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 不相交的线 (opens new window)

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

  • nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

func maxUncrossedLines(nums1 []int, nums2 []int) int {

    m, n := len(nums1), len(nums2)
    
    dp := make([][]int, m+1)
    dp[0] = make([]int, n+1)

    for i:=1; i<=m; i++ {
        dp[i] = make([]int, n+1)
        for j:=1; j<=n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 最大子数组和 (opens new window)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。

func maxSubArray(nums []int) int {
    max := nums[0]
    for i:=1; i<len(nums);i++ {
        if nums[i-1] > 0 {
            nums[i] += nums[i-1]
        }
        if max < nums[i] {
            max = nums[i]
        }
    }
    return max
}
// dp[i] = max (dp[i], dp[i] + nums[i-1])
// 这里直接拿nums数组当作dp推导了 dp := nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 判断子序列 (opens new window)

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

func isSubsequence(s string, t string) bool {
    m, n := len(s), len(t)
    if m == 0 {
        return true
    }
    dp := make([][]bool, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]bool, n+1)
    }

    for j:=0; j<n; j++ {
        dp[0][j] = true
    }

    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = (dp[i-1][j-1] || dp[i][j-1])
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 不同的子序列 (opens new window)

给你两个字符串 s** **和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

也可以归属为字符串子序列问题，删除元素本质是选 or不选，就会出现dp的状态转化

# 回文问题

# 回文子串个数

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。

image.png

func countSubstrings(s string) int {
    res, n := 0, len(s)
    dp := make([][]bool, n)
    for i:=0; i<n; i++ {
        dp[i] = make([]bool, n)
    } 

    for i:=n-1; i>=0; i-- {
        for j:=i; j<n; j++ {
            if s[i] == s[j] && (j-i<=1 || dp[i+1][j-1]) {
                res++
                dp[i][j] = true
            } 
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 最长回文子序列 (opens new window)

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i:=0; i<n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    } 

    for i:=n-1; i>=0; i-- {
        for j:=i+1; j<n; j++ {
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    return dp[0][n-1]
}

// dp五部曲
// 1. 确定dp大小，下标意义
// 2. 递推公式
// 3. 初始化
// 4. 遍历顺序
// 5. 推导dp数组, 取出最后结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 最长回文子串 (opens new window)

给你一个字符串 s，找到 s 中最长的 回文子串。

func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    
    n := len(s)
    dp := make([][]bool, n)
    for i:=0; i<n; i++ {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    l, r := 0, 0
    for i:=n-1; i>=0; i-- {
        for j:=i+1; j<n; j++ {
            if s[i] == s[j] {
                if j-i<=1 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }
            if dp[i][j] && r-l <= j-i {
                r, l = j, i
            }
        }
    }
    return s[l:r+1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 编辑距离问题

# 编辑距离 (opens new window)

给你两个单词 word1 和 word2， 请返回将 _word1_ 转换成 _word2_ 所使用的最少操作数 。 你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
    }

    // 初始化
    for i:=0; i<=m ; i++ {
        dp[i][0] = i
    }
    for j:=0; j<=n; j++ {
        dp[0][j] = j
    }

    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
            }
        }
    }
    return dp[m][n]
}

/*
dp 五步
1. 确定dp结构
2. 确定递推公式
3. 初始化
4. 遍历顺序
5. 取出结果
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 两个字符串的删除操作 (opens new window)

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2_ _相同所需的最小步数。 **每步 **可以删除任意一个字符串中的一个字符。

与编辑距离类似，只是该题不能做字符替换操作，word1[i] != word2[j]时，dp推导不能走替换操作

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
    }

    // 初始化
    for i:=0; i<=m ; i++ {
        dp[i][0] = i
    }
    for j:=0; j<=n; j++ {
        dp[0][j] = j
    }

    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 不同的子序列 (opens new window)

给你两个字符串 s** **和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

也可以归属为字符串子序列问题，删除元素本质是选 or不选，就会出现dp的状态转化

func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    dp := make([][]int, m+1)
    for i:=0; i<=m; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = 1
    }

    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[m][n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
编辑 (opens new window)
上次更新: 2024/09/13, 11:59:12
滑动窗口
贪心算法

← 贪心算法→

最近更新
01
ceph分布式存储-对象存储(RGW)搭建
10-27
02
ceph分布式存储-集群客户端连接
10-27
03
ceph分布式存储-管理crushmap
10-27
更多文章>
Theme by Vdoing