位置：首页-资讯-后端开发

动态规划详解Python

2023-09-09 12:09

短信预约 -IT技能 免费直播动态提醒

动态规划

动态规划（Dynamic Programming）是一种用于解决复杂问题的算法设计方法。它通常用于优化问题，其中问题可以被分解成一系列重叠子问题，通过存储并重复使用已经解决过的子问题的解，可以避免重复计算，从而提高算法的效率。

动态规划的基本思想是将原始问题分解成若干个子问题，并逐个求解这些子问题的最优解。通过定义状态和状态转移方程，可以将问题的求解转化为一个递推过程，从而得到最优解。

动态规划算法的核心步骤通常包括以下几个方面：

定义问题的状态：将原始问题抽象为一个或多个子问题，并定义状态来表示子问题的解。
确定状态转移方程：通过分析子问题之间的关系，建立状态之间的转移方程，描述当前状态和之前状态之间的关系。
确定初始条件：确定最简单的子问题的解，即初始状态的值。
递推求解：使用状态转移方程和初始条件，逐步计算出更复杂的子问题的解，直到得到原始问题的解。
解析解：根据子问题的解，逐步还原出原始问题的解。

动态规划算法通常具有较高的时间复杂度，但通过存储已解决的子问题的解，可以大大减少重复计算，提高算法效率。它在许多领域有广泛的应用，如组合优化、图论、序列比对、路径规划等。

斐波那契数列

这里简单的解释一下斐波那契数列：F(0) = 0 , F(1) = 1
F(N) = F(N-1) + F(N-2) , N>1 数列前几项如下：
0 1 1 2 3 5 8 13 21…

递归代码和非递归代码比较

import timedef calculate_time(func):    def wrapper(*args, **kwargs):        start_time = time.time()        result = func(*args, **kwargs)        end_time = time.time()        execution_time = end_time - start_time        print(f"函数 {func.__name__} 的执行时间为：{execution_time} 秒")        return result    return wrapper@calculate_timedef func1(n):    return _func1(n)# 存在大量的子问题重复计算def _func1(n):    if n <= 1:        return n    return _func1(n - 1) + _func1(n - 2)# 把需要用到的子问题存起来@calculate_timedef func2(n):    f = [0, 1]    if n > 1:        for i in range(n - 1):            num = f[-1] + f[-2]            f.append(num)    return f[n]print(func1(36))print(func2(36))

运行结果：
函数 func1 的执行时间为：3.150125503540039 秒
14930352
函数 func2 的执行时间为：0.0 秒
14930352

爬楼梯

问题：有一个楼梯，总共有10级台阶，每次只能走一级或者两级台阶，全部走完，有多少种走法？

找规律得到递推式：
在这里插入图片描述

def climbStairs(self, n: int) -> int:    f = [0,1,2]    if n > 2:        for i in range(n-2):            r = f[-1] + f[-2]            f.append(r)    return f[n]

最大回撤

问题：有一个数组，求其中两个数x,y，满足x的索引小于y的索引，使得 x-y 最大。例如 arr = [3,7,2,6,4,1,9,8,5]，最大回撤是6，对应的x=7,y=1。

初始时，设max_drop=0，peak都设为arr[0]。然后从左到右遍历数组，对于每个元素price：

如果price大于peak，更新peak为当前的price。
否则，计算当前的回撤值drop，即peak - price。
如果drop大于max_drop，更新max_drop为当前的drop。

最终，max_drop就是最大回撤的值。

# 只返回最大回撤的金额def calculate_max_drawdown(arr):    max_drop = 0    peak = arr[0]    for i in range(1, len(arr)):        if arr[i] > peak:            peak = arr[i]        else:            drop = peak - arr[i]            if drop > max_drop:                max_drop = drop    return max_drop# 示例用法arr = [3, 7, 2, 6, 4, 1, 9, 8, 5]max_drawdown = calculate_max_drawdown(arr)print(max_drawdown)  # 输出: 6

要求计算出最大回撤，并且对应的返回x和y
可以使用动态规划的思想来解决这个问题。我们可以定义一个变量max_sum来跟踪当前的最大子数组和，以及一个变量current_sum来记录当前的子数组和。

初始时，将max_sum和current_sum都设为数组中的第一个元素。然后从数组的第二个元素开始遍历，对于每个元素num：

将current_sum与0比较，取其中较大的值，并将num加到current_sum中，得到新的current_sum。
将current_sum与max_sum比较，取其中较大的值，并将结果赋给max_sum。

最终，max_sum就是最大连续子数组的和。

def calculate_max_drawdown(arr):    max_drop = 0    peak = 0    start_index = 0    end_index = 0    for i, price in enumerate(arr):        if price > peak:            peak = price        else:            drop = peak - price            if drop > max_drop:                max_drop = drop                start_index = arr.index(peak)                end_index = i    return max_drop, start_index, end_index# 示例用法arr = [3, 7, 2, 6, 4, 1, 9, 8, 5]max_drawdown, start_index, end_index = calculate_max_drawdown(arr)print("最大回撤：", max_drawdown)print("起始索引：", start_index)print("结束索引：", end_index)

输出：
最大回撤： 6
起始索引： 1
结束索引： 4

最大连续子数组和

问题：给定一个数组，求其最大连续子数组的和。例如：arr = [1,5,-10,2,5,-3,2,6,-3,1]. 输出为：12。对应的连续子数组为 [2,5,-3,2,6]。

def max_subarray_sum(arr):    max_sum = arr[0]    current_sum = arr[0]    for num in arr[1:]:        current_sum = max(num, current_sum + num)        max_sum = max(max_sum, current_sum)    return max_sum# 示例用法arr = [1, 5, -10, 2, 5, -3, 2, 6, -3, 1]max_sum = max_subarray_sum(arr)print(max_sum)  # 输出: 12

"""同时输出对应的子数组"""def max_subarray_sum(arr):    max_sum = arr[0]    current_sum = arr[0]    start_index = 0    end_index = 0    temp_start_index = 0    for i, num in enumerate(arr[1:], start=1):        if num > current_sum + num:            temp_start_index = i            current_sum = num        else:            current_sum = current_sum + num        if current_sum > max_sum:            start_index = temp_start_index            end_index = i            max_sum = current_sum    subarray = arr[start_index:end_index + 1]    return max_sum, subarray# 示例用法arr = [1, 5, -10, 2, 5, -3, 2, 6, -3, 1]max_sum, subarray = max_subarray_sum(arr)print("最大连续子数组和：", max_sum)print("最大连续子数组：", subarray)

输出：
最大连续子数组和： 12
最大连续子数组： [2, 5, -3, 2, 6]

最长不重复子串

题目形式：给定一个字符串，找出没有重复字符的最长的子串。例如输入“abcbefgf”，答案是 “cbefg”。

算法步骤如下：

定义两个指针，start 和 end，分别表示滑动窗口的起始位置和
结束位置，初始时两个指针都指向字符串的开头。
定义一个集合 seen，用于存储滑动窗口中出现过的字符。
定义两个变量 max_length 和 max_substring，分别用于记录最长子串的长度和内容，初始时都为 0。开始遍历字符串，从左到右依次移动 end 指针：
—a.如果当前字符 s[end] 在集合 seen 中不存在，说明是一个新的字符，将其加入 seen 中，并更新 end 指针。
—b.如果当前字符 s[end] 在集合 seen 中已经存在，说明遇到了重复字符。此时需要移动 start 指针，并更新 seen 集合，直到滑动窗口中不再有重复字符。

—c.在每次移动 end 指针时，都需要更新 max_length 和 max_substring，以记录当前的最长子串。
遍历结束后，返回最长子串 max_substring。

def longest_unique_substring(s):    start = 0    end = 0    seen = set()    max_length = 0    max_substring = ""    while end < len(s):        if s[end] not in seen:            seen.add(s[end])            end += 1        else:            if end - start > max_length:                max_length = end - start                max_substring = s[start:end]            seen.remove(s[start])            start += 1    if end - start > max_length:        max_substring = s[start:end]    return max_substring# 示例用法s = "abcbefgf"result = longest_unique_substring(s)print(result)  # 输出: "cbefg"

全排列

问题：给定一个数组，找出其所有可能的排列。例如: arr = [1,1,3]，输出为 [[1,1,3],[1,3,1],[3,1,1]]。

def permute_unique(nums):    # 定义递归函数，生成给定位置上的所有可能排列    def backtrack(start):        # 终止条件：当遍历到数组末尾时，将当前生成的排列加入结果集        if start == len(nums):            permutations.append(nums[:])  # 将当前排列加入结果集            return        # 使用一个集合来记录已经选择过的元素，避免重复生成相同的排列        used = set()        # 从当前位置开始，依次尝试每个元素作为当前位置的元素        for i in range(start, len(nums)):            # 如果当前元素已经被选择过，则跳过            if nums[i] in used:                continue            # 进行选择：将当前元素加入路径，并标记为已选择            used.add(nums[i])            nums[start], nums[i] = nums[i], nums[start]            # 递归调用自身，在新的位置上生成剩余元素的所有可能排列            backtrack(start + 1)            # 撤销选择：将当前选择的元素从路径中移除，并将其标记为未选择，以便进行下一次选择            nums[start], nums[i] = nums[i], nums[start]            used.remove(nums[i])    permutations = []  # 结果集，用于存储所有排列    backtrack(0)  # 从位置0开始生成所有排列    return permutations# 示例用法nums = [1, 1, 3]result = permute_unique(nums)print(result)

快速排序+二分查找

def partition(lst, left, right):    temp = lst[left]    while left < right:        while left < right and lst[right] >= temp:            right -= 1        lst[left] = lst[right]        while left < right and lst[left] <= temp:            left += 1        lst[right] = lst[left]    lst[left] = temp    return leftarr = [5, 2, 8, 6, 3]print(partition(arr, 0, len(arr) - 1))def quick_sort(lst, left, right):    if left < right:        mid = partition(lst, left, right)        quick_sort(lst, left, mid)        quick_sort(lst, mid + 1, right)quick_sort(arr, 0, len(arr) - 1)print(arr)#  二分查找只适用于在有序序列中查找元素def binary_search(lst, val):    left = 0    right = len(lst) - 1    while left <= right:        mid = (left + right) // 2        if lst[mid] == val:            return mid        elif lst[mid] > val:  # 说明要查找的值在mid的左边            right = mid - 1        else:  # 说明要查找的值在mid的右边、            left = mid + 1    # 代码执行至此说明没有找到元素val，返回-1    return -1# 注意：mid定义在while循环里面print(binary_search(arr, 8))

输出：
2
[2, 3, 5, 6, 8]
4

合并两个有序数组（归并排序）

题目形式：给定两个按升序排列的有序数组，将它们合并成一个新的有序数组。例如：a = [1,2,6,8], b = [2,4,7,10]，输出为 arr = [1,2,2,4,6,7,8,10]

# 定义合并函数，将两个有序序列合并为一个有序序列def merge(lst, left, mid, right):    """    思路：定义一个列表merged，循环比较两个有序序列的首元素大小，并放入临时空列表。    """    if left < right:        merged = []        i = left        j = mid + 1        while i <= mid and j <= right:            if lst[i] < lst[j]:                merged.append(lst[i])                i += 1            else:                merged.append(lst[j])                j += 1        # 代码执行至此，有一个序列元素为空，另一个不为空，接下来将剩下的元素放入空列表        while i <= mid:            merged.append(lst[i])            i += 1        while j <= right:            merged.append(lst[j])            j += 1        lst[left:right + 1] = merged        return lstdef _merge_sort(lst, left, right):    if left < right:        mid = (left + right) // 2        _merge_sort(lst, left, mid)        _merge_sort(lst, mid + 1, right)        merge(lst, left, mid, right)@calculate_timedef merge_sort(lst):    _merge_sort(lst, 0, len(lst) - 1)if __name__ == '__main__':    # 测试代码    lst = list(range(10000))    random.shuffle(lst)    print(lst)    merge_sort(lst)    print(lst)

三数之和

def sum_of_three(arr,target):    assert len(arr)>=3,"len(arr) should >=3!"    arr.sort()    ans = set()    for k,c in enumerate(arr):        i,j = k+1,len(arr)-1        while i<j:            if arr[i]+arr[j]+c <target:                i = i+1            elif arr[i]+arr[j]+c > target:                j = j-1            else:                ans.update({(arr[k],arr[i],arr[j])})                i = i+1                j = j-1    return(list(ans)) print(sum_of_three([-3,-1,-2,1,2,3],0))