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

目录

基本概念

最长递增子序列（中等）

最大子数组和（中等）

---

基本概念

重叠子问题

一个问题可以被分解为多个子问题，并且这些子问题在求解过程中会被多次重复计算。例如，在计算斐波那契数列时，斐波那契数 F(n) 的计算需要先计算 F(n - 1) 和 F(n - 2)，而计算 F(n - 1) 又需要计算 F(n - 2) 和 F(n - 3)，这里 F(n - 2) 就是重叠子问题。

最优子结构

问题的最优解可以由子问题的最优解组合而成。也就是说，如果一个问题的最优解包含了子问题的解，那么这些子问题的解本身对于它们各自的子问题来说也必须是最优的。以背包问题为例，要得到能装入背包的最大价值物品组合的最优解，这个最优解取决于装入背包部分容量时选择不同物品所得到的子问题的最优解。

解题步骤

1. 确定状态：定义问题的状态，状态通常是问题求解过程中的某个中间结果或者某个阶段的情况描述。比如在爬楼梯问题中，状态可以定义为爬到第 n 级楼梯时的不同方法数，这里的 n 就是状态变量。
2. 建立状态转移方程：根据问题的最优子结构性质，找出状态之间的递推关系，即从一个或多个已知状态推导出另一个状态的方程。在斐波那契数列问题中，状态转移方程就是 F(n) = F(n - 1) + F(n - 2)。
3. 确定边界条件：明确问题的初始状态或最小子问题的解，这些边界条件是递归求解的基础。对于斐波那契数列，边界条件是 F(0) = 0，F(1) = 1。

最长递增子序列（中等）

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 。

示例 2：

输入：nums = [1]输出：1

示例 3：

输入：nums = [5,4,-1,7,8]输出：23

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;}
}