【算法篇】逐步理解动态规划模型4（子数组问题）
目录
子数组问题
1.最大数组和
2.等差数列划分
3.单词拆分
本文旨在通过对力扣上三道题进行讲解来让大家对使用动态规划解决多状态有一定思路，培养大家对状态定义，以及状态方程书写的思维。
顺序：
题目链接-》算法思路-》代码呈现
子数组问题
动态规划类题目解题步骤：
- 依据题目进行状态表示(dp[i]的含义)
- 写出状态转移方程(类似于dp[i]=dp[i-1]+dp[i-2])
- 为防止填表时数组越界，对dp表进行初始化（dp[0]=dp[1]=1）
- 搞清楚填表顺序（从前往后或者从后往前）
- 利用dp表返回问题答案
1.最大数组和
题目链接：
https://leetcode.cn/problems/maximum-subarray/
算法思路：
1. 状态表⽰：
对于线性 dp ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
- 以某个位置为结尾，巴拉巴拉；
- 以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以「某个位置为结尾」，结合「题⽬要求」，定义⼀个状态表⽰：
dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。
2. 状态转移⽅程：
dp[i] 的所有可能可以分为以下两种：
- ⼦数组的⻓度为 1 ：此时 dp[i] = nums[i] ；
- ⼦数组的⻓度⼤于 1 ：此时 dp[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼤值再加上 nums[i] ，也就是 dp[i - 1] + nums[i] 。
由于我们要的是「最⼤值」，因此应该是两种情况下的最⼤值，因此可得转移⽅程：
dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
3. 初始化：
可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：
- 辅助结点⾥⾯的值要「保证后续填表是正确的」；
- 「下标的映射关系」。
在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = 0 即可。
4. 填表顺序：
根据「状态转移⽅程」易得，填表顺序为「从左往右」。
5. 返回值：
状态表⽰为「以 i 为结尾的所有⼦数组」的最⼤值，但是最⼤⼦数组和的结尾我们是不确定的。因此我们需要返回整个 dp 表中的最⼤值。
代码呈现：
class Solution {public int maxSubArray(int[] nums) {int n=nums.length;int[] dp=new int[n+1];dp[0]=-10000007;int re=dp[0];for(int i=1;i<=n;i++){dp[i]=Math.max(dp[i-1]+nums[i-1],nums[i-1]);re=re>dp[i]?re:dp[i];}return re;}
}2.等差数列划分
题目链接：
https://leetcode.cn/problems/arithmetic-slices/
算法思路：
1. 状态表⽰：
由于我们的研究对象是「⼀段连续的区间」，如果我们状态表⽰定义成 [0, i] 区间内⼀共有多少等差数列，那么我们在分析 dp[i] 的状态转移时，会⽆从下⼿，因为我们不清楚前⾯那么多的「等差数列都在什么位置」。所以说，我们定义的状态表⽰必须让等差数列「有迹可循」，让状态转移的时候能找到「⼤部队」。因此，我们可以「固定死等差数列的结尾」，定义下⾯的状态表⽰：
dp[i] 表⽰必须「以 i 位置的元素为结尾」的等差数列有多少种。
2. 状态转移⽅程：
我们需要了解⼀下等差数列的性质：如果 a b c 三个数成等差数列，这时候来了⼀个 d ，其中 b c d 也能构成⼀个等差数列，那么 a b c d 四个数能够成等差序列吗？答案是：显然的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解，我们就可以转⽽分析我们的状态转移⽅程了。
对于 dp[i] 位置的元素 nums[i] ，会与前⾯的两个元素有下⾯两种情况：
- nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以nums[i] 为结尾的等差数列就不存在，此时 dp[i] = 0 ；
- nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列：那么以nums[i - 1] 为结尾的所有等差数列后⾯填上⼀个 nums[i] 也是⼀个等差数列，此时dp[i] = dp[i - 1] 。但是，因为 nums[i - 2], nums[i - 1], nums[i] 三者⼜能构成⼀个新的等差数列，因此要在之前的基础上再添上⼀个等差数列，于是dp[i] = dp[i - 1] + 1 。
综上所述：状态转移⽅程为：
当： nums[i - 2] + nums[i] != 2 * nums[i - 1] 时， dp[i] = 0
当： nums[i - 2] + nums[i] == 2 * nums[i - 1] 时， dp[i] = 1 + dp[i - 1]
3. 初始化：
由于需要⽤到前两个位置的元素，但是前两个位置的元素⼜⽆法构成等差数列，因此 dp[0] = dp[1] = 0 。
4. 填表顺序：
毫⽆疑问是「从左往右」。
5. 返回值：
因为我们要的是所有的等差数列的个数，因此需要返回整个 dp 表⾥⾯的元素之和。
代码呈现：
class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;int[] dp=new int[n];for(int i=2;i<n;i++){dp[i]=(nums[i]-nums[i-1])==(nums[i-1]-nums[i-2])?dp[i-1]+1:0;}int sum=0;for(int j=0;j<n;j++){sum+=dp[j];}return sum;
}
}3.单词拆分
题目链接：
https://leetcode.cn/problems/word-break/
算法思路：
1. 状态表⽰：
对于线性 dp ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
- 以某个位置为结尾，巴拉巴拉；
- 以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：
dp[i] 表⽰： [0, i] 区间内的字符串，能否被字典中的单词拼接⽽成。
2. 状态转移⽅程：
对于 dp[i] ，为了确定当前的字符串能否由字典⾥⾯的单词构成，根据最后⼀个单词的起始位置 j ，我们可以将其分解为前后两部分：
- 前⾯⼀部分 [0, j - 1] 区间的字符串；
- 后⾯⼀部分 [j, i] 区间的字符串。
其中前⾯部分我们可以在 dp[j - 1] 中找到答案，后⾯部分的⼦串可以在字典⾥⾯找到。
因此，我们得出⼀个结论：当我们在从 0 ~ i 枚举 j 的时候，只要 dp[j - 1] = true
并且后⾯部分的⼦串 s.substr(j, i - j + 1) 能够在字典中找到，那么 dp[i] = true 。
3. 初始化：
可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：
- 辅助结点⾥⾯的值要「保证后续填表是正确的」；
- 「下标的映射关系」。
在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = true ，可以理解为空串能够拼接⽽成。
其中为了⽅便处理下标的映射关系，我们可以将字符串前⾯加上⼀个占位符 s = ' ' + s ，这样就没有下标的映射关系的问题了，同时还能处理「空串」的情况。
4. 填表顺序：
显⽽易⻅，填表顺序「从左往右」。
5. 返回值：
由「状态表⽰」可得：返回 dp[n] 位置的布尔值。
哈希表优化的⼩细节：
在状态转移中，我们需要判断后⾯部分的⼦串「是否在字典」之中，因此会「频繁的⽤到查询操作」。为了节省效率，我们可以提前把「字典中的单词」存⼊到「哈希表」中。
代码呈现：
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int n=s.length();boolean[] dp=new boolean[n+1];dp[0]=true;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){String tmp=s.substring(j,i+1);if(wordDict.contains(tmp)&&dp[j]){dp[i+1]=true;}}}return dp[n];}
}