数据结构与算法：回溯+分治+动态规划

我会带着你远行 2021-12-09 04:45 308阅读 0赞

【回溯】

1. 利用回溯算法求解八皇后问题

import random
    
    #冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上
    
    def conflict(state, nextX):
    
        nextY = len(state)
    
        for i in range(nextY):
    
            #如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放
    
            if abs(state[i]-nextX) in (0, nextY-i):
    
            # 表示如果下一个皇后和正在考虑的前一个皇后的水平距离为0或者垂直距离相等，就返回TRUE，否则返回False
    
                return True
    
        return False
    
    
    #采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。
    
    def queens(num, state=()):
    
        for pos in range(num):
    
            if not conflict(state, pos):
    
                #产生当前皇后的位置信息
    
                #如果只剩一个皇后没有放置
    
                if len(state) == num-1:
    
                    yield (pos, )
    
                #否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
    
                #程序要从前面的皇后得到包含位置信息的元组（元组不可更改）
    
                #并要为后面的皇后提供当前皇后的每一种合法的位置信息
    
                #所以把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
    
                else:
    
                    for result in queens(num, state+(pos,)):
    
                        yield (pos, ) + result
    
    
    #为了直观表现棋盘，用X表示每个皇后的位置
    
    def prettyprint(solution):
    
        def line(pos, length=len(solution)):
    
            return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
    
        for pos in solution:
    
            print line(pos)
    
        for item in queens(8):
    
            print item
    
    
    if __name__ == "__main__":
    
        prettyprint(random.choice(list(queens(8))))

2. 利用回溯算法求解 0-1 背包问题

'''0-1背包问题'''
    n = 3      # 物品数量
    c = 30      # 包的载重量
    w = [20, 15, 15] # 物品重量
    v = [45, 25, 25] # 物品价值
    maxw = 0 # 合条件的能装载的最大重量
    maxv = 0 # 合条件的能装载的最大价值
    bag = [0,0,0] # 一个解（n元0-1数组）长度固定为n
    bags = []   # 一组解
    bestbag = None # 最佳解
    # 冲突检测
    def conflict(k):
      global bag, w, c
      # bag内的前k个物品已超重，则冲突
      if sum([y[0] for y in filter(lambda x:x[1]==1, zip(w[:k+1], bag[:k+1]))]) > c:
        return True
      return False
    # 套用子集树模板
    def backpack(k): # 到达第k个物品
      global bag, maxv, maxw, bestbag
      if k==n: # 超出最后一个物品，判断结果是否最优
        cv = get_a_pack_value(bag)
        cw = get_a_pack_weight(bag)
        if cv > maxv : # 价值大的优先
          maxv = cv
          bestbag = bag[:]
        if cv == maxv and cw < maxw: # 价值相同，重量轻的优先
          maxw = cw
          bestbag = bag[:]
      else:
        for i in [1,0]: # 遍历两种状态 [选取1, 不选取0]
          bag[k] = i # 因为解的长度是固定的
          if not conflict(k): # 剪枝
            backpack(k+1)
    # 根据一个解bag，计算重量
    def get_a_pack_weight(bag):
      global w
      return sum([y[0] for y in filter(lambda x:x[1]==1, zip(w, bag))])
    # 根据一个解bag，计算价值
    def get_a_pack_value(bag):
      global v
      return sum([y[0] for y in filter(lambda x:x[1]==1, zip(v, bag))])
    # 测试
    backpack(0)
    print(bestbag, get_a_pack_value(bestbag))

【分治】

利用分治算法求一组数据的逆序对个数

class Solution:
        def InversePairs(self, data):
            if not data:
                return 0
            temp = [i for i in data]
            return self.mergeSort(temp, data, 0, len(data)-1) % 1000000007
           
        def mergeSort(self, temp, data, low, high):
            if low >= high:
                temp[low] = data[low]
                return 0
            mid = (low + high) / 2
            left = self.mergeSort(data, temp, low, mid)
            right = self.mergeSort(data, temp, mid+1, high)
               
            count = 0
            i = low
            j = mid+1
            index = low
            while i <= mid and j <= high:
                if data[i] <= data[j]:
                    temp[index] = data[i]
                    i += 1
                else:
                    temp[index] = data[j]
                    count += mid-i+1
                    j += 1
                index += 1
            while i <= mid:
                temp[index] = data[i]
                i += 1
                index += 1
            while j <= high:
                temp[index] = data[j]
                j += 1
                index += 1
            return count + left + right

【动态规划】

1. 0-1 背包问题

def bag(n, c, w, v):
        """
        测试数据：
        n = 6  物品的数量，
        c = 10 书包能承受的重量，
        w = [2, 2, 3, 1, 5, 2] 每个物品的重量，
        v = [2, 3, 1, 5, 4, 3] 每个物品的价值
        """
        # 置零，表示初始状态
        value = [[0 for j in range(c + 1)] for i in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, c + 1):
                value[i][j] = value[i - 1][j]
                # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
                if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
                    value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
        for x in value:
            print(x)
        return value
    
    def show(n, c, w, value):
        print('最大价值为:', value[n][c])
        x = [False for i in range(n)]
        j = c
        for i in range(n, 0, -1):
            if value[i][j] > value[i - 1][j]:
                x[i - 1] = True
                j -= w[i - 1]
        print('背包中所装物品为:')
        for i in range(n):
            if x[i]:
                print('第', i+1, '个,', end='')

2. 最小路径和（详细可看 Minimum Path Sum）

class Solution(object):
        def minPathSum(self, grid):
            row = len(grid)
            col = len(grid[0])
            if grid==None or row==0:
                return 0
            dp = [ [0]*col for _ in range(row)]
            #Base Case
            dp[0][0] = grid[0][0]
            for i in range(1,row):
                dp[i][0] = dp[i-1][0] + grid[i][0]
            for i in range(1,col):
                dp[0][i] = dp[0][i-1] + grid[0][i]
            #一般情况
            for i in range(1,row):
                for j in range(1,col):
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
            return dp[-1][-1]

3. 编程实现莱文斯坦最短编辑距离

import numpy
    
     
    
    def wer2(r, h):
    
        # Initialization
    
    
        #生成一个全是0的二维数组
    
        d = numpy.zeros((len(r)+1)*(len(h)+1), dtype=numpy.uint8)
    
        print(d)
    
        #此时的d形如：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
    
        #将二维数组变成n*n的格式
    
        d = d.reshape((len(r)+1, len(h)+1))
    
        print(d)
    
        #此时的的形如：
    
        """
    
        [[0 0 0 0]
    
         [0 0 0 0]
    
         [0 0 0 0]
    
         [0 0 0 0]]
    
        """
    
        #为数组两侧赋值
    
        for i in range(len(r)+1):
    
            for j in range(len(h)+1):
    
                if i == 0:
    
                    d[0][j] = j
    
                elif j == 0:
    
                    d[i][0] = i
    
        print(d)
    
        #此时的d形如：
    
        """
    
        [[0 1 2 3]
    
         [1 0 0 0]
    
         [2 0 0 0]
    
         [3 0 0 0]
    
         ]
    
        """
    
        # Computation
    
        #计算编辑距离
    
        for i in range(1, len(r)+1):
    
            for j in range(1, len(h)+1):
    
                if r[i-1] == h[j-1]:
    
                    d[i][j] = d[i-1][j-1]
    
                else:
    
                    #替换
    
                    substitution = d[i-1][j-1] + 1
    
                    #插入
    
                    insertion    = d[i][j-1] + 1
    
                    #删除
    
                    deletion     = d[i-1][j] + 1
    
                    print(substitution,insertion,deletion)
    
                    d[i][j] = min(substitution, insertion, deletion)
    
        print(d)
    
        #最终的d形如：
    
        """
    
        [[0 1 2 3]
    
         [1 1 2 3]
    
         [2 2 1 2]
    
         [3 3 2 2]]
    
        """
    
        return d[len(r)][len(h)]
    
    if __name__ == '__main__':
    
        res=wer2(['c','b','c'],['a','b','d'])
    
        print(res)

4. 编程实现查找两个字符串的最长公共子序列

# 最长公共子序列问题
    
    # 求 a,b 序列的最长公共子序列
    
    import numpy as np
    
     
    
    def lcs_len(a,b):
    
        n = len(a)
    
        m = len(b)
    
        p = n+1
    
        q = m+1
    
        c = np.zeros((p,q))
    
        val = c.copy()
    
        for i in range(1,p):
    
            for j in range(1,q):
    
                if a[i-1] == b[j-1]:
    
                    c[i,j] = c[i-1,j-1] + 1
    
                    val[i,j] = 0   # 在左上角
    
                elif c[i-1,j] >= c[i,j-1]:
    
                    c[i,j] = c[i-1,j]
    
                    val[i,j] = 1   # 在上方
    
                else:
    
                    c[i,j] = c[i,j-1]
    
                    val[i,j] = 2   # 在左方
    
        k = int(c[n,m])  # k 等于 最长公共子序列的元素个数
    
        print "k =",k
    
        G = range(k+1)   # G 用来保存最长公共子序列
    
        while k>0:
    
            if val[n,m]==1:
    
                n-=1
    
            elif val[n,m]==2:
    
                m-=1
    
            else:
    
                G[k] = a[n-1]
    
                k-=1
    
                n-=1
    
                m-=1
    
        return G[1:]
    
     
    
    a,b = [1,2,3,5,7,8,9],[1,2,3,4,5,9]
    
    h = lcs_len(a,b)
    
    print h

5. 编程实现一个数据序列的最长递增子序列

class myStack:
    
        #找出以元素i结尾的最长递增子序列
    
        #每一次为ｉ进行分配时，要检查前面所有的算法ai(i<x)
    
        #若ai小于ax，则说明ax可以跟在ai后形成一个新的递增子序列
    
        #否则，以ax结尾的递增子序列的最长长度为1
    
        def getHeight(self, men, n):
    
            longest = {}    #c存一个字典
    
            longest[0] = 1
    
            for i in range(1, len(men)):
    
                maxlen = -1
    
                for j in range(0, i):
    
                    if men[i]>men[j] and maxlen<longest[j]:
    
                        maxlen = longest[j]
    
                if maxlen>=1:    #说明之前的递增序列中，有ax可以跟的
    
                    longest[i] = maxlen +1
    
                else:
    
                    longest[i] = 1
    
            return max(longest.values())

练习：

1. 电话号码的字母组合 [https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/][https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number]

思路：字典

class Solution:
        def letterCombinations(self, digits: str) -> List[str]:
    　　　　  if len(digits) == 0:
                return []
            digit_map={
                0:'0',
                1:'1',
                2:'abc',
                3:'def',
                4:'ghi',
                5:'jkl',
                6:'mno',
                7:'pqrs',
                8:'tuv',
                9:'wxyz'
            }
            result = [""]
            for digit in digits:
                tmp_list = []
                for ch in digit_map[int(digit)]:
                    for str in result:
                        tmp_list.append(str+ch)
                result = tmp_list
            return result

2. 全排列 [https://leetcode-cn.com/problems/permutations/][https_leetcode-cn.com_problems_permutations]

思路：递归

class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
    　　　　　if len(nums)<=1:
                return [nums]
            answer = []
            for i, num in enumerate(nums):
                n = nums[:i]+nums[i+1:]
                for y in self.permute(n):
                    answer.append([num]+y)   
            return answer

3. 分割回文串 II [https://leetcode-cn.com/problems/palindrome-partitioning-ii/comments/ ][https_leetcode-cn.com_problems_palindrome-partitioning-ii_comments_]

思路：动态规划

class Solution:
        def minCut(self, s: str) -> int:
            if s == s[::-1]:  # s=[]适用
                return 0
            dp = [len(s)] * len(s)
            dp[0] = 0
            for i in range(1, len(s)):
                for j in range(i+1):
                    if s[j:i+1] == s[j:i+1][::-1]:
                        if j == 0:
                            dp[i] = 0
                        else:
                            dp[i] = min(dp[i], dp[j-1] + 1)
            return dp[-1]

4. 正则表达式匹配 [https://leetcode-cn.com/problems/regular-expression-matching/][https_leetcode-cn.com_problems_regular-expression-matching]

思路：动态规划

class Solution:
        def isMatch(self, s: str, p: str) -> bool:
    　　　　　#if not s or not p:
                #return False
            s_len = len(s)
            p_len = len(p)
            dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
            #print(dp)
            dp[0][0] = True
            for i in range(p_len):
                if p[i] == "*" and dp[0][i - 1]:
                    dp[0][i + 1] = True
            #print(dp)
            for i in range(s_len):
                for j in range(p_len):
                    if p[j] == s[i] or p[j] == ".":
                        dp[i + 1][j + 1] = dp[i][j]
                    elif p[j] == "*":
                        if p[j - 1] != s[i]:
                            dp[i + 1][j + 1] = dp[i + 1][j - 1]
                        if p[j-1] == s[i] or p[j-1] == ".":
                            dp[i+1][j+1] = (dp[i][j+1] or dp[i+1][j]   or  dp[i+1][j-1])
            #print(dp)
            return dp[-1][-1]

5. 最小路径和 [https://leetcode-cn.com/problems/minimum-path-sum/][https_leetcode-cn.com_problems_minimum-path-sum]

思路：动态规划

6. 零钱兑换 \[作为可选\] [https://leetcode-cn.com/problems/coin-change/][https_leetcode-cn.com_problems_coin-change]

7. 买卖股票的最佳时机 \[作为可选\] [https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/][https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock]

思路：动态规划

class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            if len(prices) == 0:
                return 0
            profit=0
            buy=prices[0]
            for i in range(0,len(prices)):
                buy=min(buy,prices[i])
                profit=max(profit, prices[i]-buy)
            return profit

8. 乘积最大子序列 \[作为可选\] [https://leetcode-cn.com/problems/maximum-product-subarray/][https_leetcode-cn.com_problems_maximum-product-subarray]

思路：动态规划

class Solution:
        def maxProduct(self, nums: List[int]) -> int:
            #temp记录整个数组的子序列最大连乘积        
            temp = nums[0]        
            length = len(nums)                
            #M数组记录包含当前位置的最大连乘值        
            M = [0 for i in range(length)]        
            #m数组记录包含当前位置的最小连乘值        
            m = [0 for i in range(length)]                
            for i in range(length):            
                if i == 0:                
                    M[i] = nums[i]               
                    m[i] = nums[i]            
                else:                
                    #包含当前位置的最大连乘值从：当前位置和到第i-1个元素的最大连乘值的乘积、当前位置和到第i-1个元素的最小连乘值的乘积当前元素中选出             
                    M[i] = max(max(M[i-1]*nums[i],m[i-1]*nums[i]),nums[i])                
                    m[i] = min(min(M[i-1]*nums[i],m[i-1]*nums[i]),nums[i])                            
                    temp = max(temp,M[i])                    
            return temp

9. 三角形最小路径和 \[作为可选\] [https://leetcode-cn.com/problems/triangle/][https_leetcode-cn.com_problems_triangle]

转载于:https://www.cnblogs.com/deeplearning-man/p/10884769.html

[https_leetcode-cn.com_problems_letter-combinations-of-a-phone-number]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[https_leetcode-cn.com_problems_permutations]: https://leetcode-cn.com/problems/permutations/
[https_leetcode-cn.com_problems_palindrome-partitioning-ii_comments_]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/comments/
[https_leetcode-cn.com_problems_regular-expression-matching]: https://leetcode-cn.com/problems/regular-expression-matching/
[https_leetcode-cn.com_problems_minimum-path-sum]: https://leetcode-cn.com/problems/minimum-path-sum/
[https_leetcode-cn.com_problems_coin-change]: https://leetcode-cn.com/problems/coin-change/
[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[https_leetcode-cn.com_problems_maximum-product-subarray]: https://leetcode-cn.com/problems/maximum-product-subarray/
[https_leetcode-cn.com_problems_triangle]: https://leetcode-cn.com/problems/triangle/