【数据结构与算法】动态规划

目录

动态规划

1. 基本概念

2. 基本步骤

3. 经典应用场景

4. 优点和局限性

最长递增子序列（中等）

最大子数组和（中等）

---

动态规划

动态规划是一种用于解决多阶段决策问题的算法思想，它将复杂问题分解为一系列相对简单的子问题，并通过求解子问题来逐步构建最终解。以下是关于动态规划的简单介绍：

1. 基本概念

动态规划的核心是最优子结构和重叠子问题。

• 最优子结构：一个问题的最优解可以由其子问题的最优解组合而成。例如，在最短路径问题中，从起点到终点的最短路径，必然包含从起点到中间某点的最短路径。

• 重叠子问题：在求解过程中，许多子问题会被重复计算。动态规划通过存储这些子问题的解（通常用表格），避免重复计算，从而提高效率。

2. 基本步骤

动态规划的求解过程通常包括以下步骤：

• 定义状态：确定子问题的表示方式。例如，dp[i]可以表示以第i个元素结尾的某种最优解。

• 建立状态转移方程：根据问题的性质，找到状态之间的关系。例如，dp[i] = dp[i - 1] + cost[i]。

• 初始化：确定初始状态的值，例如dp[0] = 0。

• 计算顺序：按照一定的顺序（通常是从小到大）计算各个状态的值。

• 返回最终结果：根据问题要求，从状态表中提取最终结果。

3. 经典应用场景

• 背包问题：给定一组物品，每个物品有重量和价值，背包有最大承重，目标是选择物品使得背包中物品的总价值最大。

• 最长递增子序列：在一个序列中找到最长的递增子序列。

• 斐波那契数列：计算第n个斐波那契数，动态规划可以避免递归中的重复计算。

• 矩阵链乘法：给定一组矩阵的维度，确定最优的乘法顺序以最小化乘法次数。

4. 优点和局限性

• 优点：

  • 高效性：通过存储子问题的解，避免重复计算，时间复杂度通常优于暴力搜索。

  • 适用范围广：适用于具有最优子结构和重叠子问题的多种问题。

• 局限性：

  • 空间复杂度较高：需要存储所有子问题的解，可能会占用较多内存。

  • 难以设计：状态定义和状态转移方程的设计需要一定的技巧和经验。

最长递增子序列（中等）

nums 数组，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]  输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

一维动态规划

int[] nums = {10,9,2,5,3,7,101,18};

dp默认都是1

dp[2] = 1

dp[3] = max(dp[3], dp[2]+1) = 2

dp[4] = max(dp[4], dp[2] + 1) =2

dp[5] = max(dp[5], dp[2] + 1) = 2

            max(dp[5], dp[3] + 1) = 3

            max(dp[5], dp[4] + 1) = 3

dp[6] = max(dp[6], dp[2] + 1) = 2

            max(dp[6], dp[3] + 1) = 3

            max(dp[6], dp[4] + 1) = 3

            max(dp[6], dp[5] + 1) = 4

public int lengthOfLIS(int[] nums) {if(nums.length == 1){return 1;}int max = 0;int[] dp = new int[nums.length];Arrays.fill(dp, 1);for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if(nums[i] > nums[j]){dp[i] = Integer.max(dp[i], dp[j]+1);}}max = Integer.max(max, dp[i]);}return  max;}

最大子数组和（中等）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}