动态规划#

动态规划，简称DP，是解决很多重叠子问题的有效方法，每一个状态是由上一个状态推导出来的

动态规划我们一般需要从几方面去思考：

  1. 状态转换
  2. 构造子问题

动态规划与贪心算法

动规是由前一个状态推导出来的，而贪心是局部直接选最优的

思路

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

斐波那契数列#

1 1 2 3 5……..

递归

1
2
3
4
5
6
func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func fib(n int) int {
    if n == 0 || n == 1{
        return n
    }

    //时间O(n) 空间O(1)
    
    pre2 := 0
    pre1 := 1
    curr := pre1 + pre2 //第i个数等于i-1个和i-2个数的和

    for i := 2; i <=n; i++{
        curr = pre1 + pre2
        pre2 = pre1 //更新变量,实现向右移动
        pre1 = curr
    }

    return curr
}

爬楼梯#

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路

有规律，第一层为1，第二层为2，第三层为1+2=3，第四层为2+3=5

由此一来，就是上面一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}

	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
    var i int
	for i = 3; i < n+1; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	
	return dp[n]
}

使用最小会用爬楼梯#

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

注意：

  • 从第i层开始起跳需要花费cost[i]的费用
  • 最终要跳到cost[n]层，也就是最顶层，没有费用标注
  • 可以从n=0,1出发

下面设置一个dp数组，表示到达每一层需要的费用

而每一层的费用是 上一层的起跳费用cost[i-1]/cost[i-2]+上一层的到达上一层需要的费用dp[i-1]/dp[i-2]

因此 dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

代码：

1
2
3
4
5
6
7
8
func minCostClimbingStairs(cost []int) int {
	dp := make([]int , len(cost)+1)
	dp[0],dp[1] = 0 , 0
	for i:= 2 ;i<= len(cost); i++{
		dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
	}
	return dp[len(cost)]
}

不同路径#

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路

其实我一开始想到的是回溯并写出了回溯的代码，然后超时了，唉。

那就用动态规划来写把，其实脑子想着动态规划，但是一点思路都没有，就看了代码随想录，感觉最重要的是 dp数组的确定以及index的含义

  • dp数组的确定以及index的含义

    因为要求路径不如把dp数组的值当作到达 i,j的路径数

    又因为robot只能向下，向右行驶，因此第一行和第一列都只有一条路径，最后实现

    62.不同路径1

ok，然后后面就很简单了

动态规划

我这样子写最清楚，有更加简便的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func uniquePaths(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}

	return dp[m-1][n-1]
}

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
	count := 0
	var dfs func(x, y int)
	dfs = func(x, y int) {
		if x == m-1 && y == n-1 {
			count++
			return
		}
		if x < m-1 {
			dfs(x+1, y)
		}
		if y < n-1 {
			dfs(x, y+1)
		}
	}
	dfs(0, 0)
	return count
}

不同路径||#

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

思路

这道题大体思路和上面一题一样，具体说说怎么解决障碍物的问题

  1. 边缘障碍物

    边缘障碍物主要是指最上面一层和最左边一层的障碍物，只要中间有一个障碍物出现，后面的路径都为0，显而易见

  2. 中间障碍物

    如果左边或者上面有一个为障碍物，则他的路径数就是没有障碍物的那一方的数字

代码

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
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	for i := 0; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			obstacleGrid[i][0] = 0
		} else {
			obstacleGrid[i][0] = obstacleGrid[i-1][0]
		}
	}

	for i := 0; i < n; i++ {
		if obstacleGrid[0][i] == 1 {
			obstacleGrid[0][i] = 0
		} else {
			obstacleGrid[0][i] = obstacleGrid[0][i-1]
		}
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
			}
		}
	}

	return obstacleGrid[m-1][n-1]
}

整数拆分#

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

dp 表示拆分index次情况下的最大数

  • i * (i - j) 表示不继续拆分的情况
  • i * dp[i-j] 表示继续拆分的情况，因为dp[i-j]是i-j情况下的拆分最大值，所以直接套用即可不用重新计算dp[i-j]的大小
1
2
3
4
5
6
7
8
9
10
11
func integerBreak(n int) int {
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 1
    for i := 3; i < n+1; i++ {
        for j := 1; j < i-1; j++ {
            dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))
        }
    }
    return dp[n]
}

二叉搜索树#

动态规划找到子状态之间的关系很重要！| LeetCode：96.不同的二叉搜索树_哔哩哔哩_bilibili

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

0-1背包问题#

杭电ACM刘老师-算法入门培训-第6讲-背包入门_哔哩哔哩_bilibili

这里来详细讲一下我现在重新复习对0-1背包的困惑解决吧：

0-1背包主要有 m个物品 + n 容量的背包 + 每个物品有（容量+价值） – 一般是关注前两个值来判断dp数组思路的形成

image-20241126152357699

(1,5)表示价值为1，占体积为5的物体，我们看这张二维数组的时候要时刻想着 -> 从子问题的最优化 保证 父问题的最优化

所以第二行的值可以由第一行的值推导出来，第三行的值可以由第二行的值推导出来，由于这里的第二行是由第一行的值推导出来，所以第三行简洁是由第一行和第二行的值推导出来的，这个尤为重要。

我们在计算dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]) 这个算式的时候会疑惑为什么一定是dp[i-1] 因为i-1是由1，2，3….i-2 这些行值推导出来的，i-1真正的含义是前i-1行所能包含的物品的最大价值，而不仅仅是仅限于i-1行

那么我们就可以发现 我第i行的值只需要知道第i-1行的值就可以 求出来，那么是不是我可以吧这个二维数组转换成一维数组

我可以拿着第1行–>第2行；第二行–>第三方…………..以此类推

这样子也就能理解 dp[i] = max(dp[i],dp[i-nums[i]]+nums[i]) 的含义，这里的dp[i]在未赋值前就是第i-1行的值，只有赋值完后才是第i行的最大价值

然后就是后面的逆序遍历问题了，为什么要逆序遍历？ 因为如果是正序遍历，我们先会把 dp[i] 变成 dp[i] (前者的dp[i]是i-1行时的值，后者时赋值后第i行的值)，而后来的dp[i]的计算需要 dp[i-nums[i]] 的值（这里的dp[i-nums[i]]是第i时的值，而不是第i-1时的值）就会导致重复计算，因此需要逆序遍历 —- 简单总结一下就是，右边的数的计算需要依赖左边的数，在右边的数改变之前左边的数不能改变，就是这样。

如果还不能理解，建议去看刘春英ACM的视频x

例题：

背包问题的变形

  1. 最多装 capacity，求方案数/最大价值和
  2. 恰好装 capacity，求方案数/最大价值和/最小价值和
  3. 最少装 capacity，求方案数/最小价值和

方案数： dp[j] += dp[j-nums[i]]

价值和： dp[j] = max(dp[j],dp[j-value[i]]+value[i])

听说这个问题特别重要

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

  1. 确定dp数组

    1
    dp[i][j] 表示在[0-i]中任意取物品，放进容量为j的背包中，最大的价值

  2. 递推公式

    1
    2
    // 如果不放物品  dp[i][j] = dp[i-1][j]
    // 如果放物品    dp[i][j]= dp[i-1][j-w[i]] + v[i]   //如果放物品，则背包的容量变成了 j-w[i]，因此背包为j-w[i]时的最大价值为dp[i-1][j-w[i]]，加上当前物品的价值v[i]即为dp[i][j]

  3. 初始化dp数组

    1
    2
    // dp[i][0] = 0 
    // dp[0][j] = 如果背包容量大于dp[0]就为dp[0],否则为0

代码

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
// weight 是物品的质量    capacity是背包的容量  ，不能把物品的质量当作背包的容量。
func bags(value []int, weight []int, capacity int) int {
	dp := make([][]int, len(value))
	for i := range dp {
		dp[i] = make([]int, capacity+1) // 容量0也要计算
	}
	for i := 0; i <= capacity; i++ {
		if weight[0] <= i {
			dp[0][i] = value[0]
		} else {
			dp[0][i] = 0 // 初始化容量为0时的价值为0
		}
	}

	// 先物品、后背包
	for i := 1; i < len(value); i++ {
		for j := 1; j <= capacity; j++ {
			if weight[i] > j {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
			}
		}
	}

	return dp[len(value)-1][capacity]
}

func main() {
	value := []int{15, 20, 30}
	weight := []int{1, 3, 4}
	fmt.Println(bags(value, weight, 4))
}

背包问题的单数组求解#

只使用一个数组来求解背包问题

注意点

  • dp[i]表示容量为i的背包装dp[i]的价值
  • 基本的思路还是按照二维数组的解法来做的，就是代码呈现不一样
  • 遍历顺序要倒序
  • 只使用一个数组就表示当前数组要不断被覆盖
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func test_1_wei_bag_problem(weight, value []int, bagWeight int) int {
	// 定义 and 初始化
	dp := make([]int,bagWeight+1)
	// 递推顺序
	for i := 0 ;i < len(weight) ; i++ {
		// 这里必须倒序,区别二维,因为二维dp保存了i的状态
		for j:= bagWeight; j >= weight[i] ; j-- {
			// 递推公式
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	//fmt.Println(dp)
	return dp[bagWeight]
}

分割等和子集#

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路：

一看到这道题，其实想要用回溯来做，但是danshi

动态规划的变迁

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

根据上面的变迁和之前的背包问题的基础，基本上就可以做出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func canPartition(nums []int) bool {
	partSum := 0
	for i := 0; i < len(nums); i++ {
		partSum += nums[i]
	}

	if partSum%2 != 0 {
		return false
	}

	partSum = partSum / 2

	dp := make([]int, partSum+1)
	
	for i := 0; i < len(nums); i++ {
		for j:= partSum ; j>=nums[i]; j-- {
			dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
		}
	}
	
	return dp[partSum] == partSum
}

最后一块石头的重量II#

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

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

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

思路：

可以将石头分为两堆，使得两堆石头的重量差最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func lastStoneWeightII(stones []int) int {
	partSum := 0
	for _, stone := range stones {
		partSum += stone
	}
	n := len(stones)
	m := partSum / 2

	dp := make([]int, m+1)
	for i := 0; i < n; i++ {
		for j := m; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}

	return partSum - 2*dp[m]
}

目标和#

给你一个非负整数数组 nums 和一个整数 target 。

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

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

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

思路：

理解这道题用了我很多的时间，感觉对背包问题的具体思路解决还是不太清楚

dp[i] i 表示容量 dp[i]表示大小

同时一维数组的求法中是不断的叠加，这个要注意

二刷了，现在对以前的问题来解决一下，主要是回答一下这个递推公式的形成

dp[j] = dp[j-nums[i]] 但我们考虑之前的背包问题的时候，我们会考虑这个物品取还是不取，然后求出这个最大值

但是在这个题目中dp[i]表示的是目标和为i有dp[i]种方法，因此当我不取这个物品的时候，我是到达不了这个目标和的，我只有取了这个物品，还剩下j-nums[i]，那么当我背包空间为j-nums[i]时有几种方法就不言而喻了x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
funcfindTargetSumWays(nums []int,target int)int{
	sum:=0 
	for i:=0 ;i<len(nums);i++{
		sum += nums[i]
	}
	
	if sum < Abs(target) || (sum + target)%2==1{
		return 0 
	}
	
	bag := (sum + target)/2
	dp := make([]int,bag+1)
	dp[0]=1
	
	for v := range nums[i]{
		for j:=bag;j>=nums[i];j++{
			dp[j]+=dp[j-nums[i]]
		}
	}
	
	return dp[bag]
}

零和一#

昨天因为心烦意乱所以就写了一题，这道题就没写，因为看又有1又有0

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findMaxForm(strs []string, m, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for _, s := range strs {
        zeros := strings.Count(s, "0")
        ones := len(s) - zeros
        for j := m; j >= zeros; j-- {
            for k := n; k >= ones; k-- {
                dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones]+1)
            }
        }
    }
    return dp[m][n]
}

完全背包基础#

跟0-1背包的区别就是，物品的数量没有了限制，比如说同样是一堆有价值有重量的石头，0-1背包中每个石头只能用一次，而完全背包中无限用

还有一个区别就是完全背包的遍历顺序可以颠倒，可以先遍历物品重量，再遍历价值，而0-1背包中只能先遍历价值再遍历重量

完全背包中的遍历顺序是正向的，因为之前讲过从前往后遍历会导致重复，而完全背包不怕重复，反而需要重复，因此正向

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

1
2
3
4
5
6
7
8
9
func test_CompletePack1(weight, value []int, bagWeight int) int {
	dp := make([]int, bagWeight+1)
	for i := 0; i < len(weight); i++ {
		for j := weight[i]; j <= bagWeight; j++ {
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	return dp[bagWeight]
}

下面就来做道题目吧

零钱兑换||#

我现在做动态规划已经有种，明明不理解但是还是能莫名其妙搓出来的感觉了

真不爽。。。

1
2
3
4
5
6
7
8
9
10
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]
}

组合总和Ⅳ#

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

  • 组合数

    循环的时候，先物品再背包

  • 排列数

    循环的时候，先背包再物品

为什么是这个规律，不妨我们看一下两者的区别：

1
2
3
4
for {  // 物品
	for {  // 背包
	}
}

在这种情况下，我们是先取出物品1，在背包中进行遍历，再取出物品二，在背包种进行遍历，因此最后遍历得到的顺序就是物品slice的顺序

1
2
3
4
for {  // 背包
	for {  // 物品
	}
}

而在这种情况下，我是先拿出一格背包，对所有物品进行遍历，再拿出一格背包对所有物品进行遍历，我每一格背包所取的值是随机的，因此就是排列顺序 over~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)

	dp[0] = 1
	for j:= 0 ;j<=target;j++{
		for i:=0 ;i<len(nums);i++{
			if j>=nums[i]{
				dp[j] += dp[j-nums[i]]
			}
		}
	}

	return dp[target]
}

个人建议再去看一下这两个视频

目标和 来理解组合数的求法

组合总和 来理解总共组合数和排列数的区别

爬楼梯（进阶版）#

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

思路和上题差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main
import "fmt"
func main(){
    var m,n  int
    fmt.Scan(&n,&m)
    dp:=make([]int,n+1)
    dp[0]=1
    for i:=1;i<=n;i++{
       for j:=1;j <= m;j++{
          if i-j>=0{
             dp[i]+= dp[i-j]
          }
       }
    }
    fmt.Print(dp[n])
}

零钱兑换#

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
       dp[i] = math.MaxInt32
    }
    dp[0] = 0

    for _, coin := range coins {
       for i := coin; i <= amount; i++ {
          dp[i] = min(dp[i], dp[i-coin]+1)
       }
    }

    if dp[amount] == math.MaxInt32 {
       return -1
    }

    return dp[amount]
}

完全平方数#

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路和上面一题一言

1
2
3
4
5
6
7
8
9
10
11
12
func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0
	for i := 0; i <= n; i++ {
		dp[i] = i
		for j := 1; j*j <= i; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)

		}
	}
	return dp[n]
}

单词拆分#

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func wordBreak(s string, wordDict []string) bool {
	dp := make([]bool, len(s)+1)
	dp[0] = true

	for i := 1; i <= len(s); i++ {
		for _, word := range wordDict {
			if i >= len(word) && dp[i-len(word)] && s[i-len(word):i] == word {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

背包递推公式(总结)#

来源于代码随想录，感谢!!

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

打家劫舍|#

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

记住她的前后关系就可以做了

1
2
3
4
5
6
7
8
9
func rob(nums []int) int {
	n := len(nums)
	dp := make([]int, n+1) // dp[i]表示偷到第i家能够偷得的最大金额
	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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 二刷版本的
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		if nums[0] > nums[1] {
			return nums[0]
		} else {
			return nums[1]
		}
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	if nums[1] > nums[0] {
		dp[1] = nums[1]
	} else {
		dp[1] = nums[0]
	}

	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-1], dp[i-2]+nums[i])
	}

	return dp[len(dp)-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
func rob(nums []int) int {
    if len(nums)==0{
        return 0
    }
    if len(nums)==1{
        return nums[0]
    }
    rob1 := nums[1:]
    rob2 := nums[:len(nums)-1]

    value1 :=  robbed(rob1)
    value2 :=  robbed(rob2)
    if value1 > value2{
        return value1
    }
    return value2
}

func robbed(nums []int) int {
	n := len(nums)
	dp := make([]int, n+1) 
	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]
}

打家劫舍|||#

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金

思路：

树形DP，dp[0]表示没有盗取的最高金额，dp[1]表示盗取了的最高金额

思路一羊，不过形式比较新颖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func rob(root *TreeNode) int {
    res := dfs(root)
    return max(res[0],res[1])
}

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

    left := dfs(root.Left)
    right := dfs(root.Right)

    selected:= root.Val + left[1] + right[1]
    notSelected := max(left[0],left[1]) + max(right[0],right[1])

    return []int{selected,notSelected}
}

买卖股票的最佳时机#

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) int {
	dp := make([][]int, len(prices))
	for i, _ := range dp {
		dp[i] = make([]int, 2)
	}

	dp[0][0] = -prices[0]
	dp[0][1] = 0

	for i := 1; i < len(dp); i++ {
		dp[i][0] = max(dp[i-1][0], -prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
	}

	return dp[len(dp)-1][1]
}

买卖股票的最佳时机||#

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

dp[i][0]表示持有股票的最大金额

dp[i][1]表示不持有股票的最大金额

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    status := make([]int, len(prices) * 2)
    for i := range dp {
        dp[i] = status[:2]
        status = status[2:]
    }
    dp[0][0] = -prices[0]
    
    for i := 1; i < len(prices); i++ {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
    }
    
    return dp[len(prices) - 1][1]
}

买卖股票的最佳时机|||#

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

一天一共就有五个状态，

  1. 没有操作 （其实我们也可以不设置这个状态）
  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
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] = dp[i-1][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]
}

买卖股票的最佳时机4#

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// buy[k] 表示 最多进行k次买入的最大价值
// sell[k] 表示 最多进行k次卖出的最大价值
func maxProfit(k int, prices []int) int {
    n := len(prices)

    var buy = make([]int,k+1)
    for i:= 0 ; i <= k ; i++ {
        buy[i] = math.MinInt
    }

    var sell = make([]int,k+1)

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

买卖股票的最佳时机放含冷冻期#

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

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

二刷后：#

动态规划主要注重的是状态的转移，只要搞清楚这个题目有几个状态并且这些状态之间是如何转移的就可以进行操作，分析一下这个题目可以看到整个股票有这么几种状态，并可以直接通过状态看出状态转移的公式

1
2
3
4
5
6
7
8
// analyze the status
// 0. 持有股票的日子
// 1. 不持有股票的日子
// 2. 不持有股票且处于冷冻期的日子
// dp[i][j] 表示第 i 天，状态为 j 时的最大收益
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
// dp[i][1] = max(dp[i-1)[1], dp[i-1][2])
// dp[i][2] = dp[i-1][0] + prices[i]

现在我们再考虑一下初始化的值就可以提交了：

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
func maxProfit(prices []int) int {
    length := len(prices)
    if length == 0 {
       return 0
    }

    dp := make([][]int, length)

    for i := 0; i < length; i++ {
       dp[i] = make([]int, 3)
    }

    for i := 0; i < length; i++ {
       if i == 0 {
          dp[i][0] = -prices[i]
          dp[i][1] = 0
          dp[i][2] = 0
          continue
       }

       dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
       dp[i][1] = max(dp[i-1][1], dp[i-1][2])
       dp[i][2] = dp[i-1][0] + prices[i]
    }

    return max(dp[length-1][1], dp[length-1][2])
}

买卖股票的最佳时机含手续费#

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

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

股票问题总结#

一般做法就是设置一个列为2或者符合题意的数字

子序列问题#

  • 最长递增子序列
  • 最长连续递增序列
  • 最长重复子数组
  • 最长公共子序列

总结起来就是：

  1. 单个数组的最大连续与非连续子序列
  2. 两个数组的共同最大连续与非连续子序列

注意点：

算子序列问题的时候答案一般不会是 dp[n-1]，因为中间会有断层，条件不合格就会恢复默认值

同时算子序列一般需要再重新遍历一遍 j-i d

最长递增子序列#

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的

子序列

dp[i]表示 i 之前包括i的以nums[i]结尾的最长递增子序列的长度

具体的过程为：

以 [10, 9, 2, 5, 3, 7, 101, 18]为例

  • i=1时，取的序列为[10],因此dp[1]=1
  • i=2时，取的序列为[10,9],先算出这个子序列的最大长度，同时还要跟之前子序列的比较，取最大值，依次递推………….

ans代表的就是每次的长度的最大长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func lengthOfLIS(nums []int) int {
	dp := make([]int, len(nums))

	for k, _ := range dp {
		dp[k] = 1
	}
	ans := dp[0]
	for i := 1; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[j]+1, dp[i])
			}
		}
		if ans < dp[i] {
			ans = dp[i]
		}
	}

	return ans
}

最长连续递增序列#

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

其实这个我自己用暴力递归求解出来了(根本感受不到动规)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func findLengthOfLCIS(nums []int) int {
	ans := 1
	for i := 0; i < len(nums); i++ {
		cnt := 1
		for j := i; j < len(nums)-1; j++ {
			if nums[j] < nums[j+1] {
				cnt++
			} else {
				break
			}
		}
		if ans < cnt {
			ans = cnt
		}
	}
	return ans
}

好吧给出来的代码也没有用到动态规划

二刷后#

其实是用到递归的好吧，以前的我太蠢了

每次用到递归的时候我们都需要理解一下递归的本质是状态转移，在这道题目中的状态很明显就是 到i前的数量为dp[i]

那么if nums[i] == nums[i-1] { dp[i] = dp[i-1] +1 }

如果其中某个值不相等了，dp[i]又会变成1，因此我们需要使用res来记录中间最大值，而不是直接return dp[len(nums)-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func findLengthOfLCIS(nums []int) int {
	dp := make([]int, len(nums))

	for i, _ := range dp {
		dp[i] = 1
	}
	
	var res = 1 
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i - 1] {
			dp[i] = dp[i - 1] + 1
		} else {
			dp[i] = 1
		}
		
		if dp[i] > res {
			res = dp[i]
		}
	}
	
	return res
}

最长重复子数组#

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

dp[i][j] 表示的是 以下标为i-1 的字符串A和B重复的字符串数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findLength(nums1 []int, nums2 []int)int{
	m,n := len(nums1),len(nums2)
	dp := make([][]int,m+1)
	for i:=0;i<=m;i++{
		dp[i] = make([]int,n+1)
	}
	
	res := 0
	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
			}
			if dp[i][j] > res{
				res = dp[i][j]
			}
		}
	}
	return res
}

最长公共子序列#

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

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

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

dp[i][j] 表示的是 以下标为i-1 的字符串A和B重复的字符串数量

这里相对于上面一题的区别就是，两个数组并不会同步推进index，所以当text[i-1]!=text[j-1]的时候，就需要继承之前d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func longestCommonSubsequence(text1 string, text2 string) int {
	t1 := len(text1)
	t2 := len(text2)
	dp:=make([][]int,t1+1)
	for i:=range dp{
		dp[i]=make([]int,t2+1)
	}

	for i := 1; i <= t1; i++ {
		for j := 1; j <=t2; j++ {
			if text1[i-1]==text2[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[t1][t2]
}

不相交的线#

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

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

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

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

思路：

这道题就是求 公共的最长子序列

下面开始复习一下子序列： [1,2]与[2,1]并不是一样的序列，他们公共的子序列是

1或者是2，从这个示例可以看出，子序列本身就是有顺序的，也会保证我的线不会相交

所以这道题的解题方式就是上面一题的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxUncrossedLines(nums1 []int, nums2 []int) int {
	m, n := len(nums1), len(nums2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i, num1 := range nums1 {
		for j, num2 := range nums2 {
			if num1 == num2 {
				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]
}

最大子数组和#

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

子数组是数组中的一个连续部分。

个人觉得这道题就是动态规划的入门题，没必要放在这么后面

1
2
3
4
5
6
7
8
9
10
11
12
func maxSSubArray(nums []int) int {
	dp := make([]int, len(nums)+1)

	ans := nums[0]

	for i := 1; i <= len(nums); i++ {
		dp[i] = max(dp[i-1]+nums[i-1], nums[i-1])
		ans = max(ans, dp[i])
	}

	return ans
}

判断子序列#

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

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

详细解法看 最长重复子数组 这道题，上面有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isSubsequence(s string, t string) bool {
	// dp[i][j] 表示 s 的前 i-1 个字符是否可以由 t 的前 j-1 个字符组成

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

	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(t); j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			}else{
				dp[i][j] = dp[i][j-1]
			}
		}
	}
	
	return dp[len(s)][len(t)] == len(s)
}

两个字符串的删除操作#

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

逆向思维：求出两个字符串的最长重复子序列的长度，然后减一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func minDistance(word1 string, word2 string) int {
	t1 := len(word1)
	t2 := len(word2)
	dp:=make([][]int,t1+1)
	for i:=range dp{
		dp[i]=make([]int,t2+1)
	}

	for i := 1; i <= t1; i++ {
		for j := 1; j <=t2; j++ {
			if word1[i-1]==word2[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 len(word1)+len(word2)-2*dp[t1][t2]
}

正向推导：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func minDistance(word1 string, word2 string) int {
	dp := make([][]int, len(word1)+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, len(word2)+1)
	}
	
	for i := 0; i < len(dp); i++ {
		dp[i][0] = i
	}
	for j := 0; j < len(dp[0]); j++ {
		dp[0][j] = j
	}
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[i]); j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+2)
			}
		}
	}
	return dp[len(dp)-1][len(dp[0])-1]
}

编辑距离#

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

思路

不如思考一下，同时操作 word1和word2 与 只操作 word1 ，他们俩的次数是相同的嘛？

答案是一样的。

当word1删除时，相当于word2在增加，下面用这个思想去思考这道题

dp[i][j] 表示的是 以下标为i-1 的字符串A和B需要的步数

  • 第一种情况：

    • 插入：不如看作word2的删除，因此dp[i][j]=dp[i][j-1]+1
    • 删除：就是word1的删除，因此dp[i][j]=dp[i-1][j-1]+1

  • 第二种情况：

    • 替换：替换后的结果就是达到 word1[i-1]=word2[j-1]的状态，因此也就可出等式：

      dp[i][j]=dp[i-1][j-1]+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
func minDistance(word1 string, word2 string) int {
	m := len(word1)
	n := len(word2)
	
	dp := make([][]int, m+1)
	for i , _ := range dp{
        dp[i] = make([]int,n+1)
    }

	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for i := 0; i <= n; i++ {
		dp[0][i] = i
	}

	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], dp[i-1][j], dp[i][j-1]) + 1
			}
		}
	}
	
	return dp[m][n]
}

回文子串#

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

dp[i][j] 表示以 i 为结尾，j为初始位置的子串是否回文

如果不明白这个限定条件，就画个图，就清楚了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func countSubstrings(s string) int {
	dp := make([][]bool, len(s))
	// dp[i][j] i 是结束位置 j 是开始位置

	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}

	count := 0
	for i := 0; i < len(s); i++ {
		for j := 0; j <= i; j++ {
			if s[i] == s[j] && (i-j <= 2 || dp[i-1][j+1]) {
				dp[i][j] = true
				count++
			}
		}
	}

	return count
}

最长回文子序列#

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

记住逆序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func longestPalindromeSubseq(s string) int {
	dp := make([][]int, len(s))

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

	for i := len(s) - 1; i >= 0; i-- {
		for j := i + 1; j < len(s); 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][len(s)-1]
}

总结#