面试问题浓缩总结
小游
2021-03-24

动态规划

# 算法解释

这里我们引用一下维基百科的描述：“动态规划（Dynamic Programming, DP）在查找有很多 重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问 题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划 保存递归时的结果，因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能 完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”

通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问 题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规 划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。 同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。这一技巧笔者将在 之后的题目中介绍。

在一些情况下，动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录的 意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍 历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的，即先解决子问题，再解 决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索 到同一个子问题则进行状态记录，防止重复计算。如果题目需求的是最终状态，那么使用动态搜 索比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。

# 基本动态规划 一维

# 爬楼梯

70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210317191207204

动态规划难就难在如何找出状态方程。

这里我们每次可走一步或者两步，所以我们每阶的方法数其实就是i-1阶和i-2阶的方法数相加。所以我们的状态转移方程为 dp[i] = dp[i-1] + dp[i-2]

func climbStairs(n int) int {
   // 如果步数小于等于2，那么我们直接返回n
   if n <= 2 {
      return n
   }
   // 初始化dp数组并全部赋值为1
   dp:=make([]int,n+1)
   for k:=range dp{
      dp[k] = 1
   }
   // 这里我们计算每集阶楼梯所需要的步数
   for i := 2; i <= n; i++ {
      // 这个就是关键了，我们需要列出状态方程
      // 因为我们的状态方程是第 i-1 或 i-2这两层的方法数
      dp[i] = dp[i-1] + dp[i-2]
   }
   return dp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

不过实际上我们不需要专门搞一个数组，可以直接简化为三个边量就可以了

func climbStairs(n int) int {
   if n < 2 {
      return n
   }
   a,b,c:=1,1,1
   for i:=2;i<=n;i++ {
      a = b + c
      c = b
      b = a
   }
   return a
}
1
2
3
4
5
6
7
8
9
10
11
12

# 打家劫舍

198. 打家劫舍 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210317193401418

动态规划问题的难点就在于如何计算出状态转移方程，这里我看了一下题解，知道了状态转移方程却还是搞不懂，到后面看了代码才发生是自己思考的方式有问题，既然多个问题很难想，那我们就假设只有一家，那么结果很简单，然后我们的房子一步步加，我们可以得到这样一个规律，如果我们打劫上一家的总收益比打劫这家和上第二家的收益大的话，那么我们这家不打劫就可以了

func rob(nums []int) int {
   if len(nums)==0 {
      return 0
   }
   n:= len(nums)
   dp:=make([]int,n+1)
   // 当我们只抢劫一个房子时，结果就是num[0]
   dp[1] = nums[0]
   // 这个dp就是当有n个房子时的最大收益，我们分别开始计算
   for i := 2; i <= n; i++ {
      // 最大收益计算的关键部分就在这里了，当[i-1] 大于 num[i-1]+dp[i-2]时
      // 也就是当我们打劫前一家的收益比打劫当前这家和前第二家的收益更大时，这家我们就不打劫
      if dp[i-1] > nums[i-1]+dp[i-2] {
         dp[i] = dp[i-1]
      } else {
         dp[i] = nums[i-1]+dp[i-2]
      }
   }
   return dp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

当然，我们也可以进行压缩，不使用数组

func rob(nums []int) int {
   if len(nums) == 0 {
      return 0
   }
   a,b,c:=0,0,0
   n:=len(nums)
   // 这里我们直接从0开始计算
   for i:=0;i<n;i++ {
      if b > nums[i]+c {
         a=b
      } else {
         a=c+nums[i]
      }
      c=b;b=a
   }
   return a
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 等差数列划分（看起来简单，就是不知道原理）

413. 等差数列划分 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210319102103711

这题目一言难尽。。。。先暂时跳过。

func numberOfArithmeticSlices(nums []int) int {
   if len(nums) < 3 {
      return 0
   }
   // 初始化dp数组
   dp:=make([]int,len(nums))
   // 遍历我们的nums，来计算dp数组
   for i := 2; i < len(nums); i++ {
      // 当前位置是否符合等差数列的定义
      if nums[i]-nums[i-1] == nums[i-1] - nums[i-2] {
         // 如果满足，那么dp就为上个dp+1
         dp[i] = dp[i-1]+1
      }
   }
   sum:=0
   // 计算dp数组和
   for _,v:=range dp{
      sum+=v
   }
   return sum
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我来通俗·地解释下，dp[i]中i即为以i结尾的等差数列的个数，原问题可以拆分为原数列中以i结尾的等差数列之和。观察和分析可知，如果一个满足条件A[i] - A[i - 1] == A[i - 1] - A[i - 2]则证明i和之前的数列构成新的等差数列，如果之前以i-1结尾的等差数列为dp[i-1]个，那么以i结尾的等差数列的个数为dp[i -1] + 1，递推表达式得出则原问题解决。

# 基本动态规划 二维

# 最小路径和

image-20210319112635319

这个题目的难点还是在于状态方程，首先明确一点，我们的路径是只能向下或者向右，所以我们可以知道第一列和第一行的值肯定是前面的累加，后面任意一个点的和其实就是上面或者右边中任意一个较小的值，下面这个gif很形象也很好理解

test

func minPathSum(grid [][]int) int {
	m,n:=len(grid),len(grid[0])
	// 首先我们可以计算第一行和第一列
	// 因为我们只能向下或者向右移动所以这一行和第一列是前面的累加
	for i := 1; i < m; i++ {
		grid[i][0] += grid[i-1][0]
	}
	for i := 1; i < n; i++ {
		grid[0][i] += grid[0][i-1]
	}
	// 遍历计算后面的dp值
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			// 第i和j的位置最小值其实就是上面或者左边 中选一个最小的
			grid[i][j] = min(grid[i-1][j],grid[i][j-1])
		}
	}
	return grid[m-1][n-1]
}

func min(a int,b int) int  {
	if a > b {
		return b
	} else {
		return a
	}
}
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

# 01矩阵

542. 01 矩阵 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210319190322041

这题的状态转移方程我想出来了，但是代码没写出来一开始我是同时比较上下左右，但是没有意识到当我们第一扫描时，只能确定上和左，所以扫描下和右是没用的，还会造成错误答案。

第二次我意识到了要扫描两次，但是我居然还同时判断上左同时满足条件，实际上我们要分开判断，而且还必须和自身进行比较，因为我们第一次扫描的 时候可能已经是最优值了，没有必要从其他两个方向选最小的

func updateMatrix(matrix [][]int) [][]int {
   m,n:=len(matrix),len(matrix[0])
   // 初始化数组
   dp:=make([][]int,m)
   for i:=0;i<m;i++{
      dp[i] = make([]int,n)
   }
   // 为了方便，我们先把所有的都设为int的最大值，方便后面比较
   for i:=0;i<m;i++ {
      for j := 0; j < n; j++ {
         dp[i][j] = math.MaxInt32
      }
   }
   // 这个东西的状态转移方程比较简单就是从上下左右四个反向中找到一个最小的
   // 不过我们第一次遍历是从左上扫描到右下，所以这里我们只能获取上和左这两个方向
   // 所以我们这里需要扫描两次，完成上下左右这四个方向
   for i:=0;i<m;i++{
      for j:=0;j<n;j++{
         // 如果当前位置为0，那么结果就是0
         if matrix[i][j] == 0 {
            dp[i][j] = 0
         } else {
            // 在确定最小值时我们先确保上和左可以访问并和自身比较
            // 这里为什么要和自身比较呢，因为一开始我们dp值就是最大的
            // 然后这里我们是分别比较了上和左，所以我们需要使用dp[i][j]来临时存储最小的值
            // 最后就是我们第二次扫描时，可能第一次扫描时当前值已经是最小的了，所以我们就没有必要非要从另外两个方向比较
            if i > 0 {
               dp[i][j] = min(dp[i][j],dp[i-1][j]+1)
            }
            if j > 0 {
               dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
            }
         }
      }
   }
   // 下面这个就是从右下扫描到左上，找出下和右中最小的值
   for i:=m-1;i>=0;i--{
      for j:=n-1;j>=0;j--{
         // 因为我们第一次扫描的时候已经知道0了，所以这里没有必要再次比较
         if matrix[i][j] != 0 {
            if i+1 < m {
               dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
            }
            if j+1 < n {
               dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
            }
         }
      }
   }
   return dp
}

func min(a int,b int) int {
   if a > b {
      return b
   } else {
      return a
   }
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

# 最大正方形（待做）

221. 最大正方形 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 分割类型题

# 完全平方数

279. 完全平方数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210319194959574

这题目告诉我们千万不要使用思维定势来解题，我一直以为状态方程比较的是相邻的位置，但是实际上我们不止是比较相邻的位置，我们还可以比较i-k^2的位置，比如这里我们的状态转移方程实际上就是dp[i]=1 + min(dp[i-1], dp[i-4], dp[i-9] · · · )

func numSquares(n int) int {
   dp:=make([]int,n+1)
   for k:=range dp{
      dp[k] = math.MaxInt32
   }
   dp[0] = 0
   for i := 1; i <= n; i++ {
      for j := 1; j*j <= i; j++ {
         // 这个状态转移方程比的不是相邻的而是比i-k^2的位置
         dp[i] = Min(dp[i],dp[i-j*j]+1)
      }
   }
   return dp[n]
}

func Min(a int,b int) int {
   if a > b {
      return b
   } else {
      return a
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 解码方法（待做）

91. 解码方法 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 单词拆分（待做）

139. 单词拆分 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 子序列问题

# 最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210320101359782

这题目其实还算是简单的，只要理解了原理之后。。。

这个和前面的完全平方数不同，这里的动态规划实际上是需要重新遍历一次的，因为我们只要满足递增子序列，我们就必须算进去，所以我们需要进行双层for循环，第二层是从头开始继续遍历，只要满足条件并且长度比当前的长，我们就计算进去。

func lengthOfLIS(nums []int) int {
   max,n:=0,len(nums)
   if n <= 1 {
      return n
   }
   // 初始情况，我们设置所有dp的数组为1
   dp:=make([]int,n)
   for i:=range dp{
      dp[i] = 1
   }
   // 这里我们需要使用两层循环来进行遍历
   for i := 0; i < n; i++ {
      // 这里一层for循环是以为我们这个是求递增的子序列
      // 为了获取到所有情况，所以我们这里使用dp数组来实现
      for j := 0; j < i; j++ {
         // 只要i的值大于j，这个时候我们就可以说序列是递增的
         if nums[i] > nums[j] {
            // 然后我们只需要比较一下，找出最大的一个就可以了
            dp[i] = Max(dp[i],dp[j]+1)
         }
      }
      // 这里我们实时更新一下max的值
      max = Max(max,dp[i])
   }
   return max
}

func Max(a int,b int) int  {
   if a > b {
      return a
   } else {
      return b
   }
}
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

# 最长公共子序列（待做）

1143. 最长公共子序列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 背包问题

背包问题是一种组合优化的 NP 完全问题：有 N 个物品和容量为 W 的背包，每个物品都有 自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物 品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

# 分割等和子集

416. 分割等和子集 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210320111220891

这题目不是很好解释，等我把大概算法过一遍再来整理

func canPartition(nums []int) bool {
   n := len(nums)
   if n < 2 {
      return false
   }
   sum, max := 0, 0
   // 这里我们计算总数的时候还需要顺便计算最大值
   for _, v := range nums {
      sum += v
      if v > max {
         max = v
      }
   }
   // 判断是否可以平分为两部分
   if sum%2 != 0 {
      return false
   }
   // 计算我们的目标值
   target := sum / 2
   // 当最大值大于目标值时，一定是不能再分的
   if max > target {
      return false
   }
   // 初始化一个dp数组，一维对应数组的个数，二维对应我们背包问题的目标值
   dp := make([][]bool, n)
   for i := range dp {
      dp[i] = make([]bool, target+1)
   }
   // 默认情况下，当我们的目标值为0时，一定可以满足
   for i := 0; i < n; i++ {
      dp[i][0] = true
   }
   // 然后就是当i为0时，我们只能存放nums[0]这个元素，此时当我们的目标值为num[0]时，也满足条件
   dp[0][nums[0]] = true
   // 这里我们开始计算dp数组（注意0已经计算好了，我们从1开始）
   for i := 1; i < n; i++ {
      // 获取当前的值
      v := nums[i]
      // 从1开始挨个计算目标值为j的情况下，放i个元素可能的结果
      for j := 1; j <= target; j++ {
         // 当我们目标值大于i当前值时
         if j >= v {
            // 我们可以判断一下如果i小于1，是否可以满足条件
            // 或者前面一个恰好放入v时满足条件
            dp[i][j] = dp[i-1][j] || dp[i-1][j-v]
         } else {
            dp[i][j] = dp[i-1][j]
         }
      }
   }
   return dp[n-1][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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 一和零（待做）

474. 一和零 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 零钱兑换（待做）

322. 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 字符串编辑

# 编辑距离

72. 编辑距离 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

image-20210325102550453

这题个人感觉难点就在于如何理解动态规划，比如我们这里使用一个二维数组，一维就是第一个字符串，二维是第二个字符串，我们要做的就是把dp数组给填完。

如果要修改这么多字符串肯定很难，我们可以从最简单的开始，首先我们第一个字符串从只有一位开始，然后我们第二个字符也是从第一位逐次加到全部，在遍历的过程中，有下面这三种情况

1.当我们选择修改时，需要修改的次数是dp[i-1][j-1]（这个自己理解吧）
2.当我们选择插入 j 位置/删除 i 位置时，需要修改的次数为 dp[i-1][j] + 1
3.当我们选择插入 i 位置/删除 j 位置时，需要修改的次数为 dp[i][j-1] + 1
1
2
3

然后就是从这三个操作中找出代价最小的那一个，就是当前的最优解

func minDistance(word1 string, word2 string) int {
	m,n := len(word1),len(word2)
	// 创建dp数组一维表示第一个字符串，二维表示第二个字符串
	dp:=make([][]int,m+1)
	for i := 0; i <=m; i++ {
		dp[i] = make([]int,n+1)
	}
	// 准备计算
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			// 当i等于0时，表示第一个字符串没有内容
			// 所以我们如果想转换为第二个字符串时，需要操作j次（此时第二个字符串长度为j）
			if i == 0 {
				dp[i][j] = j
			} else if j == 0 {
				// 当j等于0时，表示第二个字符串为空
				// 如果我们需要转为第二个字符串，需要操作i次（就是删除i次，第一个字符串长度为i）
				dp[i][j] = i
			} else {
				var eq int
				// 判断当前位置的字符串是否相同(注意，数组的长度从0开始，所以我们要-1)
				if word1[i-1] == word2[j-1] {
					eq = 0
				} else {
					eq = 1
				}
				// 这里我们需要考虑三种情况
				// 1.当我们选择修改时，需要修改的次数是dp[i-1][j-1]（这个自己理解吧）
				// 2.当我们选择插入 j 位置/删除 i 位置时，需要修改的次数为 dp[i-1][j] + 1
				// 3.当我们选择插入 i 位置/删除 j 位置时，需要修改的次数为 dp[i][j-1] + 1
				dp[i][j] = min(dp[i-1][j-1]+eq,min(dp[i-1][j]+1,dp[i][j-1]+1))
			}
		}
	}
	return dp[m][n]
}
func min(a int,b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
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
36
37
38
39
40
41
42
43

# 两个键的键盘（待做）

650. 只有两个键的键盘 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 正则表达式匹配（待做）

10. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 股票交易

股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需 要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。

# 买卖股票的最佳时机

image-20210325133858483

额。。。我服了，我还以为这题用动态规划来解，还一直在研究怎么用动态规划（最后看了一下别人的代码，当场自闭）。

这题其实非常简单，就是首先要找出一个最低价股票然后买入，最后我们依次判断当前价格卖出得到的结果是不是最高的，如果是设置一下最大值，然后继续往下直到遍历整个数组。

func maxProfit(prices []int) int {
   // sell表示利润
   sell:=0
   // buy表示我们买入的价格，这里我们取负，后面计算利润可以直接相加即可
   buy:=math.MinInt32
   // 遍历整个数组
   for _,v:=range prices{
      // 首先找到一个最低价格买入
      buy = max(buy,-v)
      // 判断当前卖出是否可以获得最大利润
      sell = max(sell,buy+v)
   }
   // 返回最大利润
   return sell
}

func max(a int,b int) int {
   if a > b {
      return a
   } else {
      return b
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 买卖股票的最佳时机 IV

188. 买卖股票的最佳时机 IV - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

编辑 (opens new window)
上次更新: 2021/03/25, 23:10:37
各种搜索
分治法解题

← 分治法解题→

Theme by Vdoing | Copyright © 2021-2021 小游