带你读《图解算法小抄》二十一、动态规划（11）https://developer.aliyun.com/article/1347952?groupCode=tech_library
2）解题步骤
为了计算最长数对链，我们可以使用动态规划的思想来解决问题。排序：首先对给定的数对列表按照第二个数字的升序进行排序，以确保后面的数对始终满足跟随关系。
- 定义状态：我们可以将问题转化为对于每个数对的状态，即以该数对为结尾的最长数对链的长度。令 dp[i] 表示以第 i 个数对为结尾的最长数对链的长度。
- 初始状态：对于每个数对，初始状态为 1，即自身形成长度为 1 的数对链。
- 状态转移方程：对于第 i 个数对，我们需要找到所有在它之前的数对 (a, b)，其中 b < c，并更新 dp[i]。如果存在多个满足条件的数对，我们选择最长的数对链长度进行更新。
- 综上所述，我们可以得到状态转移方程为：dp[i] = max(dp[j] + 1)，其中 0 ≤ j < i 且 pairs[j][1] < pairs[i][0]。
- 最终解：问题的解即为所有 dp[i] 中的最大值。
下面是使用动态规划解决最长数对链问题的算法框架：
function findLongestChain(pairs) { const n = pairs.length; // 排序 pairs.sort((a, b) => a[1] - b[1]); // 初始化状态数组 const dp = new Array(n).fill(1); // 计算最长数对链的长度 for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (pairs[j][1] < pairs[i][0]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // 返回最长数对链的长度 return Math.max(...dp); }
19.最大和的循环子数组
1）题目描述
给定一个由整数数组 nums 组成的循环数组，找到具有最大和的连续子数组（允许循环）。子数组最少包含一个元素。
2）解题步骤
为了解决循环子数组的最大和问题，我们可以使用动态规划的思想来解决。处理普通的最大和子数组问题：首先，我们可以使用动态规划来解决普通的最大和子数组问题，即找到不循环的情况下的最大和子数组。我们可以使用 Kadane's 算法来处理此问题。
处理循环的最大和子数组问题：对于循环数组，存在两种情况：
- 情况一：最大和子数组不包含循环的起始点和结束点。在这种情况下，我们可以直接应用步骤 1 中的动态规划算法来计算最大和。
- 情况二：最大和子数组包含循环的起始点和结束点。在这种情况下，我们需要使用两次动态规划算法来计算最大和：
- 第一次，我们计算从数组起始位置到数组的倒数第二个位置的最大和，即 maxSum1 = kadane(nums, 0, n-2)，其中 kadane() 是步骤 1 中的动态规划算法。
- 第二次，我们计算从数组的第二个位置到数组的末尾位置的最大和，即 maxSum2 = kadane(nums, 1, n-1)。取最大和：最后，我们比较两个情况下的最大和，即 maxSum = max(maxSum1, maxSum2)，其中 max() 是取两个数的较大值的函数。
下面是使用动态规划解决最大和的循环子数组问题的算法框架：
function maxSubarraySum(nums) { // 计算不循环的最大和子数组 function kadane(arr, start, end) { let maxSum = -Infinity; let currSum = 0; for (let i = start; i <= end; i++) { currSum = Math.max(arr[i], currSum + arr[i]); maxSum = Math.max(maxSum, currSum); } return maxSum; } const n = nums.length; // 情况一：最大和子数组不包含循环的起始点和结束点 const maxSum1 = kadane(nums, 0, n - 2); // 情况二：最大和子数组包含循环的起始点和结束点 const maxSum2 = kadane(nums, 1, n - 1); // 取最大和 const maxSum = Math.max(maxSum1, maxSum2); return maxSum; }
带你读《图解算法小抄》二十一、动态规划（13）https://developer.aliyun.com/article/1347949
