数据结构-7-递归、回溯、分治、动态规划

递归

通过LeetCode上【70. 爬楼梯】学习（建议）

方法一：斐波拉切（用时28 ms，击败了99.36%的用户）

观察发现是斐波拉切数，代码如下

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        else:
            ans = [1, 1]
            for i in range(2, n + 1):
                ans.append(ans[i - 2] + ans[i - 1])
            return ans[-1]

方法二：使用递归（超时）

这道题自顶向下的思考：如果要爬到n台阶，有两种可能性:

在n-1的台阶处爬一层台阶

在n-2的台阶处爬两层台阶

继续向下延伸思考，到达每一次层一共有几种方法这个问题就变成了2个子问题：

到达n-1层台阶有几种方法

到达n-2层台阶有几种方法

之后对返回子问题之和即可。

因为递归的时候出现了很多次重复的运算。如爬n-2层的计算出现了2次，这种重复计算随着input的增大，会出现的越来越多，时间复杂度也会将以指数的级别上升。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 1
        if n == 2: return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

方法三：动态规划

优化方法二，将之前的计算好了的结果存起来，之后如果遇到重复计算直接调用结果，效率将会从之前的指数时间复杂度，变成O(N)的时间复杂度。

class Solution(object):
    def climbStairs(self, n):
        if n == 1: return 1
        res = [0 for i in range(n)]
        res[0], res[1] = 1, 2
        for i in range(2, n):
            res[i] = res[i-1] + res[i-2]
        return res[-1]

参考：https://leetcode.com/problems/climbing-stairs/discuss/163347/Python-3000DP-or-tm

回溯

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

def place(x, k): #判断是否冲突
    for i in range(1, k):
        #x[i] == x[k]判断是否为同一行
        # abs(x[i] - x[k]) == abs(i - k)判断是否在k个的对角线上
        if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k):
            return False
    return True
def queens(n):
    k = 1    #设置初始皇后为第一个
    x = [0 for row in range(n + 1)]# 设置x列表初始值为0
    while k > 0:
        x[k] = x[k] + 1 # 在当前列的下一列开始
        while (x[k] <= n) and (not place(x, k)): # 不满足条件，继续搜索下一列位置
            x[k] = x[k] + 1
        if x[k] <= n:# 判断是否为最后一个，不是就执行下一行
            if k == n:# 是最后一个皇后，退出
                break
            else: # 不是，则处理下一行皇后
                k = k + 1   #执行下一行
                x[k] = 0    #初始化，从第一列开始
        else:#n列均不满足，回溯到上一行
            x[k] = 0    #初始化列到第一列
            k = k - 1   #回溯到上一行
    return x[1:]    #返回1-8个皇后的位置
print(queens(8))

简洁解法可参考： https://blog.csdn.net/handsomekang/article/details/41308993 （简洁，用一维数组表达坐标）

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

#n个物体的重量(w[0]无用)
w = [5,8,13,27,14]
#n个物体的价值(p[0]无用)
p = [5,8,13,27,14]
#计算n的个数
n = len(w)
#背包的载重量
m = 33

dp = [[-1 for j in range(m + 1)] for i in range(n)]

for i in range(n):
    dp[i][0] = 0

for j in range(m + 1):
    if w[0] <= j:
        dp[0][j] = p[0]
    else:
        dp[0][j] = 0


def dp_fun(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if j >= w[i]:
        dp[i][j] = max(dp_fun(i-1, j), dp_fun(i-1, j-w[i]) + p[i])
    else:
        dp[i][j] = dp_fun(i-1, j)
    return dp[i][j]

print('最大值为：' + str(dp_fun(n - 1, m)))

分治

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

def merge_sort(data):
    if len(data) <= 1:
        return data
    index = len(data) // 2
    lst1 = data[:index]
    lst2 = data[index:]
    left = merge_sort(lst1)
    right = merge_sort(lst2)
    return merge(left, right)


def merge(lst1, lst2):
    """to Merge two list together"""
    list = []
    while len(lst1) > 0 and len(lst2) > 0:
        data1 = lst1[0]
        data2 = lst2[0]
        if data1 <= data2:
            list.append(lst1.pop(0))
        else:
            global num
            num = num + 1
            list.append(lst2.pop(0))
    if len(lst1) > 0:
        list.extend(lst1)
    else:
        list.extend(lst2)
    return list


num = 0
arr = [1, 3, 5, 2, 4]
print(merge_sort(arr))

动态规划

0-1 背包问题

def bag(space,n,costs,values):
    """
    递归动态规划求解0/1规划
    :param :space 背包的总容量,int
    :param :n 表示物品的总数
    :param :costs 每个物品消耗的空间，list
    :param :values 每个物品的价值，list
    """
    costs.insert(0,0)  # 下标为0的值不使用
    values.insert(0,0) # 下标为0的值不使用
    # 构建一个行数为背包容量，列数为可用物品的矩阵 PS. 行或列下标为0的值均不用
    matrix = [[0 for _ in range(n+1)] for _ in range(space+1)]
    for i in range(1,space+1):  # 从小背包推到大背包
        for j in range(1,n+1):  # 遍历所有的物品
            if i >= costs[j]:  # 考虑拿这个物品的情况和不拿这个物品的情况哪个更好
                matrix[i][j] = max(matrix[i][j-1], matrix[i - costs[j]][j-1] + values[j])
            else: # 如果装不下, 那就相当于没有这个物品
                matrix[i][j] = matrix[i][j-1]
    return matrix[-1][-1]  # 返回最终值

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

def minPathSum(self, grid):
    m = len(grid)
    n = len(grid[0])
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[-1][-1]

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

dp[i][j]表示word1[0…i-1]到word2[0…j-1]的编辑距离。而dp[i][0]显然等于i，因为只需要做i次删除操作就可以了。同理dp[0][i]也是如此，等于i，因为只需做i次插入操作就可以了。dp[i-1][j]变到dp[i][j]需要加1，因为word1[0…i-2]到word2[0…j-1]的距离是dp[i-1][j]，而word1[0…i-1]到word1[0…i-2]需要执行一次删除，所以dp[i][j]=dp[i-1][j]+1；同理dp[i][j]=dp[i][j-1]+1，因为还需要加一次word2的插入操作。如果word[i-1]==word[j-1]，则dp[i][j]=dp[i-1][j-1]，如果word[i-1]!=word[j-1]，那么需要执行一次替换replace操作，所以dp[i][j]=dp[i-1][j-1]+1

class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
        m=len(word1)+1; n=len(word2)+1
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(n):
            dp[0][i]=i
        for i in range(m):
            dp[i][0]=i
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(0 if word1[i-1]==word2[j-1] else 1))
        return dp[m-1][n-1]

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

方法一：递归

def lcs(X, Y, m, n): 
  
    if m == 0 or n == 0: 
       return 0; 
    elif X[m-1] == Y[n-1]: 
       return 1 + lcs(X, Y, m-1, n-1); 
    else: 
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
  
  
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X , Y, len(X), len(Y))

方法二：动态规划

def lcs(X , Y): 
    m = len(X) 
    n = len(Y) 
  
    L = [[None]*(n+1) for i in xrange(m+1)] 

    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 : 
                L[i][j] = 0
            elif X[i-1] == Y[j-1]: 
                L[i][j] = L[i-1][j-1]+1
            else: 
                L[i][j] = max(L[i-1][j] , L[i][j-1]) 
  
    return L[m][n] 
  
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)

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

方法一：二分

class Solution(object):
def lengthOfLIS(self, nums):
    def search(temp, left, right, target):
        if left == right:
            return left
        mid = left+(right-left)/2
        return search(temp, mid+1, right, target) if temp[mid]<target else search(temp, left, mid, target)
    temp = []
    for num in nums:
        pos = search(temp, 0, len(temp), num)
        if pos >=len(temp):
            temp.append(num)
        else:
            temp[pos]=num
    return len(temp)

方法二：动态规划

class Solution(object):
def lengthOfLIS(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    dp = [1]*len(nums)
    for i in range (1, len(nums)):
        for j in range(i):
            if nums[i] >nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)