算法篇：动态规划（一）

站长

2024年04月01日 09:26 · 阅读数 4

一. 初识动态规划

动态规划是一种通过将复杂问题分解为简单子问题来解决问题的方法。它通常用于解决具有重叠子问题和最优子结构的问题。动态规划的关键思想是将问题分解为一系列子问题，然后自底向上地解决这些子问题，并将解决方案存储在表格中，以避免重复计算。

动态规划的应用场景非常广泛，可以抽象为以下几种：

最优化问题：动态规划可以用于解决各种最优化问题，如背包问题、最长公共子序列、最短路径问题等。
计数问题：动态规划可以用于解决计数问题，例如计算给定序列的不同排列组合数量。
决策问题：动态规划可以用于解决决策问题，如股票买卖时机的选择、工作调度等。
概率问题：动态规划可以用于解决概率问题，如赌博游戏中的胜率计算、随机过程中的期望值计算等。

二. leetcode 典型应用

leetcode55 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入： nums = [2,3,1,1,4]
输出： true
解释： 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入： nums = [3,2,1,0,4]
输出： false
解释： 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

func canJump(nums []int) bool {
   if len(nums) == 0 {
      return true
   }
   maxPos := 0
   for idx,step := range nums {
      if idx > maxPos {
         return false
      }
      maxPos = max(idx+step,maxPos)
   }
   return true
}

func max(x,y int) int {
   if x>y {
      return x
   }
   return y
}

代码逻辑如下：

如果数组nums长度为0，表示没有需要跳跃的位置，直接返回true。
初始化maxPos变量为0，用于记录当前能到达的最远位置。
遍历数组nums，对于每个位置idx和它的步数step：
- 如果当前位置idx大于maxPos，说明前面的位置无法跳跃到当前位置，返回false。
- 更新maxPos为idx+step和maxPos中的较大值，表示从当前位置出发能够到达的最远位置。
如果能够完成遍历，说明可以到达最后一个位置，返回true。

max函数用于比较两个整数并返回较大的一个。

这个函数的时间复杂度为O(n)，因为它只需要遍历一次数组。空间复杂度为O(1)，因为它只使用了常数级别的额外空间。

leetcode45 跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

func jump(nums []int) int {
    minStepDp := make([]int, len(nums))
    for idx, step := range nums {
        for i := 1; i <= step; i++ {
            if idx+i >= len(nums) {
                break
            }
            if minStepDp[idx+i] == 0 {
                minStepDp[idx+i] = minStepDp[idx] + 1
            } else {
                minStepDp[idx+i] = min(minStepDp[idx]+1, minStepDp[idx+i])
            }
        }
    }
    return minStepDp[len(nums)-1]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

在这段代码中，minStepDp数组用于存储到达每个位置的最小跳跃次数。对于数组nums中的每个元素，我们检查从当前位置idx能跳跃的最大步数step，并更新idx+i位置的最小跳跃次数。最终返回到达数组最后一个位置的最小跳跃次数。

leetcode1143 最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 **是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入： text1 = "abcde", text2 = "ace" 
输出： 3  
解释： 最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入： text1 = "abc", text2 = "abc"
输出： 3
解释： 最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入： text1 = "abc", text2 = "def"
输出： 0
解释： 两个字符串没有公共子序列，返回 0 。

func longestCommonSubsequence(text1 string, text2 string) int {
   if len(text1) == 0 || len(text2) == 0 {
      return 0
   }
   dp := make([][]int,len(text1)+1)
   for idx:= range dp {
      dp[idx] =make([]int,len(text2)+1)
   }
   for i := 1 ; i <len(text1)+1;i++ {
      for j := 1;j <len(text2)+1;j++ {
         if text1[i-1] == text2[j-1] {
            dp[i][j] = dp[i-1][j-1]+1
         } else {
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
         }
      }
   }
   return dp[len(text1)][len(text2)]
}

func max(x,y int) int {
   if x > y {
      return x
   }
   return y
}

这段代码的核心思想基于动态规划的两个主要特点：重叠子问题和最优子结构。

重叠子问题：
- 问题可以分解为多个小规模但结构相同的子问题。
- 通过解决每个子问题并存储结果，可以避免重复计算，提高效率。
最优子结构：
- 一个问题的最优解包含其子问题的最优解。
- 在最长公共子序列问题中，任何两个字符串的LCS长度可以通过比较它们最后一个字符的匹配情况，并结合前一步的LCS长度来确定。

代码实现的主要思想步骤如下：

初始化状态数组：创建一个二维数组dp，其中dp[i][j]表示字符串text1的前i个字符与字符串text2的前j个字符的最长公共子序列的长度。
填充状态数组：
- 遍历两个字符串的所有字符组合。
- 当两个字符匹配时，表明当前字符可以成为LCS的一部分，因此dp[i][j]等于之前最长序列的长度加1（即dp[i-1][j-1] + 1）。
- 当两个字符不匹配时，取两个可能的最长序列中的较大者作为当前的最长序列，即dp[i][j]是dp[i-1][j]和dp[i][j-1]中的较大值。
返回结果：数组的最后一个元素dp[len(text1)][len(text2)]就是整个问题的解，即两个字符串的最长公共子序列的长度。

这个解法不仅计算了LCS的长度，同时也通过dp数组间接地记录了构建LCS所需的所有信息。如果需要具体的LCS序列，可以从dp数组的最后一个元素开始，根据转移方程反向追踪。