亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全，請及時綁定郵箱和手機立即綁定

動態規劃入門詳解：輕松掌握基礎算法

概述

动态规划是一种通过将问题分解为更小的子问题来求解复杂问题的算法思想，它通过存储子问题的解来避免重复计算，从而提高算法的效率。动态规划在算法设计、组合优化等多个领域有广泛应用，例如路径规划、字符串处理和资源分配等问题。文章详细介绍了动态规划的核心概念、应用场景以及优化技巧，并提供了经典案例和练习题。

动态规划简介

动态规划（Dynamic Programming, DP）是一种通过将问题分解为更小的子问题来求解复杂问题的算法思想。它是通过存储子问题的解来避免重复计算，从而提高算法的效率。动态规划通过利用已经计算过的子问题的结果，避免了重复计算，从而提高了算法的性能。

什么是动态规划

动态规划是一种用于解决具有最优子结构和重叠子问题特性的优化问题的算法。在动态规划中，一个问题被分解成更小的子问题，并且这些子问题的解被存储下来，以供以后使用。这种存储方式通常通过一个表格或数组来实现，这个表格会记录每个子问题的解。动态规划通常用于优化问题，它通过分析问题的最优子结构来寻找全局最优解。

动态规划的应用场景

动态规划在许多领域都有应用，特别是在算法设计、组合优化、机器学习、计算机视觉等领域。例如，动态规划可以用于解决以下问题：

  1. 路径规划问题：寻找从起点到终点的最短路径。
  2. 字符串处理问题：例如，最长公共子序列（Longest Common Subsequence, LCS）问题。
  3. 背包问题：在给定容量的背包中选择最佳物品组合。
  4. 资源分配问题：例如，任务调度问题，分配资源以最小化成本或最大化收益。
  5. 博弈论：例如，Nim 游戏和其他博弈问题。

动态规划与分治法的区别

动态规划与分治法都是将问题分解为更小的子问题来解决的方法，但两者之间存在关键区别：

  • 分治法：分治法将问题分解为互不重叠的子问题，递归地求解这些子问题，然后合并这些子问题的解来解决问题。例如，快速排序和归并排序就是分治法的典型应用。分治法的简单示例代码如下：

    def merge_sort(arr):
  if len(arr) > 1:
      mid = len(arr) // 2
      left_half = arr[:mid]
      right_half = arr[mid:]

      merge_sort(left_half)
      merge_sort(right_half)

      i = j = k = 0

      while i < len(left_half) and j < len(right_half):
          if left_half[i] < right_half[j]:
              arr[k] = left_half[i]
              i += 1
          else:
              arr[k] = right_half[j]
              j += 1
          k += 1

      while i < len(left_half):
          arr[k] = left_half[i]
          i += 1
          k += 1

      while j < len(right_half):
          arr[k] = right_half[j]
          j += 1
          k += 1
  • 动态规划：动态规划也是将问题分解为子问题，但这些子问题之间可能存在重叠。动态规划通过存储子问题的解来避免重复计算，并且通常使用表格或数组来记录这些解。动态规划的简单示例代码如下： 
    def fib(n):
  if n <= 1:
      return n
  dp = [0] * (n + 1)
  dp[0], dp[1] = 0, 1
  for i in range(2, n + 1):
      dp[i] = dp[i - 1] + dp[i - 2]
  return dp[n]

动态规划的核心概念

动态规划的核心概念包括最优子结构、重叠子问题和状态与状态转移方程。

最优子结构

最优子结构是指一个问题的最优解可以由子问题的最优解构建。在动态规划中，最优解通常可以通过递归地构建子问题的最优解来实现。换句话说，如果一个子问题的解是全局最优解的一部分，那么这个子问题的解也是最优的。例如，在寻找最长递增子序列的问题中，最长递增子序列可以通过更小的最长递增子序列构建。示例代码如下：

  def lengthOfLIS(nums):
      if not nums:
          return 0

      dp = [1] * len(nums)

      for i in range(len(nums)):
          for j in range(i):
              if nums[i] > nums[j]:
                  dp[i] = max(dp[i], dp[j] + 1)

      return max(dp)

重叠子问题

重叠子问题是指在递归求解问题时，某些子问题会被重复计算多次。动态规划通过存储这些子问题的解来避免重复计算，从而提高算法效率。例如，在计算斐波那契数列时，如果直接使用递归，会发现相同的斐波那契数会被重复计算多次。通过使用动态规划，可以避免这种重复计算。示例代码如下：

  def fib(n):
      if n <= 1:
          return n
      dp = [0] * (n + 1)
      dp[0], dp[1] = 0, 1
      for i in range(2, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]
      return dp[n]

状态与状态转移方程

在动态规划中，状态表示问题的某个特定阶段。状态转移方程用于描述如何从一个状态转移到另一个状态。状态通常用一个或多个变量表示，状态转移方程则描述了状态之间的关系。例如，在背包问题中，状态可以表示为当前的剩余容量和已经选择的物品集合。状态转移方程则描述了如何从一个容量和物品集合转移到另一个容量和物品集合。示例代码如下：

  def knapsack(capacity, weights, values, n):
      dp = [0] * (capacity + 1)

      for i in range(n):
          for j in range(capacity, weights[i] - 1, -1):
              dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

      return dp[capacity]

动态规划的基本步骤

动态规划的一般步骤包括确定状态、确定状态转移方程、确定遍历顺序、初始化边界值和计算结果。每一步都需要仔细考虑，确保算法的正确性和高效性。

确定状态

状态是问题的核心，它需要明确表示问题的一个特定阶段。例如，在爬楼梯问题中，状态可以表示为到达第n个楼梯的步数。确定状态是动态规划的关键步骤之一，它直接影响后续步骤的实现。示例代码如下：

  def climbStairs(n):
      if n <= 1:
          return n

      dp = [0] * (n + 1)
      dp[0], dp[1] = 0, 1

      for i in range(2, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]

      return dp[n]

状态转移方程

状态转移方程描述了如何从一个状态转移到另一个状态，通常是递归的。它定义了在给定当前状态的情况下，如何计算下一个状态。例如，在爬楼梯问题中，状态转移方程可以是 dp[i] = dp[i-1] + dp[i-2]，表示到达第i个楼梯的方法数等于到达第i-1个楼梯的方法数加上到达第i-2个楼梯的方法数。示例代码如下：

  def climbStairs(n):
      if n <= 1:
          return n

      dp = [0] * (n + 1)
      dp[0], dp[1] = 0, 1

      for i in range(2, n + 1):
          dp[i] = dp[i - 1] + dp[i - 2]

      return dp[n]

确定遍历顺序

遍历顺序决定了状态转移方程的计算顺序。常见的遍历顺序包括从左到右、从上到下、从底向上等。例如，在爬楼梯问题中，可以从前向后遍历楼梯，也可以从后向前遍历楼梯。

初始化边界值

边界值是指问题的初始状态，通常需要明确初始化。例如，在爬楼梯问题中，边界值可以是 dp[0] = 0 和 dp[1] = 1，表示到达第0个和第1个楼梯的方法数。

计算结果

计算结果是动态规划的最终输出。根据确定的状态、状态转移方程、遍历顺序和边界值，计算得到最终的结果。例如，在爬楼梯问题中，计算结果是 dp[n]，表示到达第n个楼梯的方法数。

动态规划的经典案例

动态规划有许多经典的应用案例，下面将详细介绍三个经典案例：爬楼梯问题、0-1背包问题和最长递增子序列问题。

爬楼梯问题

爬楼梯问题是动态规划的一个经典应用。假设有一个楼梯，你每次可以向上爬1个或2个台阶，求从第0级台阶到第n级台阶的总方法数。

  • 状态定义：dp[i] 表示到达第i级台阶的方法数。
  • 状态转移方程：dp[i] = dp[i-1] + dp[i-2]，表示到达第i级台阶的方法数等于到达第i-1级台阶的方法数加上到达第i-2级台阶的方法数。
  • 边界值：dp[0] = 0 和 dp[1] = 1，表示到达第0级和第1级台阶的方法数分别为0和1。
  • 计算顺序：从前向后遍历，从0到n。

示例代码如下：

def climbStairs(n):
    if n == 0:
        return 1
    if n == 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

0-1背包问题

0-1背包问题是动态规划的另一个经典应用。假设有一个背包和若干物品，每个物品都有一个重量和一个价值，背包有固定的容量，求在不超过背包容量的前提下，能够装入背包的最大价值。

  • 状态定义：dp[i][j] 表示在前i个物品中选取，且背包容量为j时的最大价值。
  • 状态转移方程：
    • 如果不选择第i个物品：dp[i][j] = dp[i-1][j]
    • 如果选择第i个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]
    • 取其中的最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
  • 边界值：dp[0][j] = 0 和 dp[i][0] = 0，表示没有物品时的最大价值为0。
  • 计算顺序：从前向后遍历物品，从满容量到0。

示例代码如下：

def knapsack(capacity, weights, values, n):
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])

    return dp[n][capacity]

最长递增子序列问题

最长递增子序列问题是指在给定一个序列时，找到其中最长的递增子序列。递增子序列是指序列中的子序列元素满足递增关系。

  • 状态定义：dp[i] 表示以第i个元素结尾的最长递增子序列的长度。
  • 状态转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 arr[j] < arr[i]。
  • 边界值：dp[i] = 1，表示以每个元素结尾的最长递增子序列的初始长度为1。
  • 计算顺序：从前向后遍历数组，从0到n。

示例代码如下：

def lengthOfLIS(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

动态规划的优化技巧

动态规划在实现过程中可能会遇到一些效率问题，例如时间复杂度较高或空间复杂度较高。以下是一些优化技巧，可以帮助提高动态规划算法的性能。

时间优化：空间换时间

通过空间换时间的优化技巧，可以减少重复计算的时间。例如，在爬楼梯问题中，可以通过只存储前两个状态的值来避免使用整个数组，从而将空间复杂度从O(n)降低为O(1)。同样，在其他问题中也可以通过类似的技巧进行优化。示例代码如下：

def climbStairs(n):
    if n == 0:
        return 1
    if n == 1:
        return 1

    prev1 = 1
    prev2 = 1

    for i in range(2, n + 1):
        temp = prev1
        prev1 = prev1 + prev2
        prev2 = temp

    return prev1

空间优化：滚动数组

滚动数组是一种常用的空间优化技巧。在许多问题中，当前状态只依赖于前一状态或前几状态。通过使用滚动数组可以减少存储空间。滚动数组的核心思想是只保留当前状态和前一状态或前几状态的值，从而减少空间复杂度。示例代码如下：

def knapsack(capacity, weights, values, n):
    dp = [0] * (capacity + 1)

    for i in range(1, n + 1):
        for j in range(capacity, weights[i-1] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i-1]] + values[i-1])

    return dp[capacity]

状态压缩

状态压缩是指通过改变状态的表示方式来减少状态的数量，从而减少计算量。例如，在0-1背包问题中，可以通过改变状态的表示方式将二维数组转换为一维数组，从而减少空间复杂度。示例代码如下：

def knapsack(capacity, weights, values, n):
    dp = [0] * (capacity + 1)

    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[capacity]

动态规划的实战练习

动态规划是一个需要大量练习才能熟练掌握的算法思想。本节将介绍一些动态规划问题的分类，分析常见的错误，并推荐一些练习题。

动态规划问题的分类

动态规划问题可以分为以下几类：

  1. 线性序列问题：例如，最长递增子序列、最长公共子序列等问题。
  2. 二维状态问题：例如，0-1背包问题、最大子数组和等问题。
  3. 区间问题：例如，最长递增子序列的长度、最长公共子串等问题。
  4. 状态转移问题：例如，斐波那契数列、爬楼梯等问题。

动态规划常见错误分析

在动态规划的实现过程中，经常会遇到各种错误，例如：

  1. 状态定义错误：状态定义不清晰，导致状态转移方程无法正确计算。
  2. 状态转移方程错误：状态转移方程不够准确，导致计算结果不正确。
  3. 边界值错误：边界值定义不正确，导致初始状态计算错误。
  4. 遍历顺序错误：遍历顺序不正确，导致状态转移方程计算顺序错误。

练习题推荐与解答

  • 问题1：爬楼梯问题

    • 题目描述：假设你有一个楼梯，每次可以向上爬1个或2个台阶，求从第0级台阶到第n级台阶的总方法数。

    • 解答：

      def climbStairs(n):
if n == 0:
    return 1
if n == 1:
    return 1

prev1 = 1
prev2 = 1

for i in range(2, n + 1):
    temp = prev1
    prev1 = prev1 + prev2
    prev2 = temp

return prev1

  • 问题2：0-1背包问题

    • 题目描述：有一个背包和若干物品，每个物品都有一个重量和一个价值，背包有固定的容量，求在不超过背包容量的前提下，能够装入背包的最大价值。

    • 解答：

      def knapsack(capacity, weights, values, n):
dp = [0] * (capacity + 1)

for i in range(n):
    for j in range(capacity, weights[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

return dp[capacity]

  • 问题3：最长递增子序列问题

    • 题目描述：给定一个序列，求其中最长递增子序列的长度。

    • 解答：

      def lengthOfLIS(nums):
if not nums:
    return 0

dp = [1] * len(nums)

for i in range(len(nums)):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

通过这些练习题，可以更好地理解和掌握动态规划的关键概念和步骤。推荐通过慕课网等网站进行更多的练习和学习。

點擊查看更多內容
為 TA 點贊

若覺得本文不錯，就分享一下吧！

評論

作者其他優質文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習，寫下你的評論
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

 幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

 公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消