0%

机试——动态规划和回溯法

发表于 更新于 阅读次数： Valine：
本文字数： 1k 阅读时长 ≈ 1 分钟

动态规划DP

​ 基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

​ 核心：找到递推公式

二维递归

1.背包问题
2.分割等和子数组(也会背包问题)

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

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
4
5
输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

​ 本题是一个经典的动态规划问题的题型——0/1背包问题,背包的大小为sum(nums)/2。该问题首先要我们初始化一个数组w，w[i]代表能否将背包填充到i，而能将背包填充到i有两种方式，一种是直接使用i大小的块，第二是使用多个小块，因此我们可以总结出递推公式：

​ w[i] = w[i]||w[i-num]

​ 这个递推公式用程序表示就是：

1
2
3
for num in nums:
  for i in range(c, num - 1, -1):
      w[i] = w[i] or w[i - num]

​ 举例来说：

​ 对于输入[1,5,11,5]来说，
​ 当num=1时，通过递推式只能得到w[1]=true
​ 当num=5时，通过递推式能够得到w[5]=true,w[6]=true，因为可以通过1+5组合
​ 当num=5时，通过递推式能够得到新的w[11]=true（5+6=11）
​ 当num=11时，没有新改动w
​ 所以此时可以发现w[11]=true，所以可以等分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canPartition(self, nums) -> bool:
        # 计算总价值
        c = sum(nums)
        # 奇数直接排除
        if c % 2 != 0:
            return False
        c = c // 2
        w = [False] * (c + 1)
        # 第0个位置设置为true，表示当元素出现的时候让w[i-num]为True,也就是w[i]为True
        w[0] = True
        for num in nums:
            for i in range(c, num - 1, -1):
                w[i] = w[i] or w[i - num]

        return w[c]

​ 当然本题也就可以使用BST，但是时间复杂度太高，leetcode没过

回溯法-深度优先搜索BST

​ 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

​ 核心：暴力遍历

1.求解一个集合的全部子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

​ 找子集相关问题的BST基本上采用的核心思想：每个位置都可能出现采用或者不采用两种情况，而如果可能出现重复的元素，那么就要事先将原数组进行排序，存进result之前判断是否已有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        def core(nums,i,tmp):
            if i==length:
                result.append(tmp)
                return 
            #每次向后遍历时有两种情况，一种是将当前节点值加入到tmp中，一种是不加入
            core(nums,i+1,tmp+[nums[i]])
            core(nums,i+1,tmp)
            
        nums.sort()
        length = len(nums) 
        result = []
        core(nums,0,[])
        
        return result

拓展：含重复的子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        def core(nums,i,tmp):
            if i==length:
                if tmp not in result: 
                    result.append(tmp)
                return
            
            core(nums,i+1,tmp)
            core(nums,i+1,tmp+[nums[i]])
            
        length = len(nums)
        result = []
        nums.sort()   #这里必须要先排序
        core(nums,0,[])
        return result
2.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def core(nums,tmp):
            if nums==[]:
                result.append(tmp)
                return 
            
            for num in nums:
                s = nums[::]
                s.remove(num)
                core(s,tmp+[num])
                
        result = []
        core(nums,[])
            
        return result

拓展：含重复数组的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        
        def core(nums,tmp):
            if nums==[]:
                if tmp not in result:
                    result.append(tmp)
                return
            
            for num in nums:
                s = nums[::]
                s.remove(num)
                core(s,tmp+[num])
                
        
        result = []
        nums.sort()
        core(nums,[])
        return result
3.划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

1
2
3
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
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
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
				
        if k == 1:
            return True
        #如果不能被k整除，那么直接无解
        sum_num = sum(nums)
        if sum_num % k != 0:
            return False
          
        avg = sum_num // k 
        nums.sort(reverse=True)
        
        n = len(nums)
        if n < k :return False
        visited = set()   #标志位，标志哪个位置已经被使用过了

        def dfs(k,tmp_sum,loc):
          	#当选用的几个数之和等于目标值，那么k减一，再找下一个子集
            if tmp_sum == avg:
                return  dfs(k-1,0,0)
            #如果k==1，由于上面已经验证过可以被k整除，因此一定成立
            if k == 1:
                return True
            for i in range(loc,n):
                if i not in visited and nums[i] + tmp_sum <= avg:
                    visited.add(i)
                    if dfs(k,tmp_sum+nums[i],i+1):
                        return True
                    visited.remove(i)
            return False
        return dfs(k,0,0)