1. 优化思路
2. 滚动数组
3. 斜率优化
思路：
- 临近的几个值是否能代表枚举行为，俗称找规律
- 如果有枚举行为，通过画表、举例的方式找到规律，将复杂度优化到O(1)
3.1 数字裂开
题目：
给定一个正数1，裂开的方式有一种，（1）
给定一个正数2，裂开的方式有两种，（1，1）（2）
给定一个正数3，裂开的方式有三种，（1，1，1）（1，2）（3）
给定一个正数4，裂开的方式有五种，（1，1，1，1）（1，1，2）（1，3）（2，2）和（4）
给定一个正数n，求裂开的方式有几种
递归：
/**
* 可变参数：pre为上一次裂开后的数，剩余rest需要裂开
*
* 方法含义：剩余rest需要刚好裂开(且上一个裂开的数据是pre)的方法数
* 无后效性：rest裂开后的数据需要大于pre (pre 之前的数子都没有rest裂开后大)
* @return
*/
private int process(int pre, int rest){
//base case, 如果rest刚好为0，那么返回裂开方法数1
if(rest == 0){
return 1;
}
//边界：rest还没有之前裂开的pre大，那么返回裂开方法数为0，代表该裂开方案无效
if(rest < pre){
return 0;
}
int ways = 0;
//从之前pre开始裂开
for (int i = pre; i <= rest; i++) {
//裂开后，返回给我：基于i，剩余rest-i的刚好裂开的方法数
ways += process(i, rest - i);
}
return ways;
}
动态规划：
private int processDp(int num){
//1.问题定义
//dp[pre][rest], 剩余rest需要刚好裂开(且上一个裂开的数据是pre)的方法数
//rest: 0~num, 大小为num + 1, pre: 1~rest, 大小：num + 1
int [][]dp = new int[num + 1][num + 1];
//2.边界
for (int pre = 0; pre <= num; pre++) {
dp[pre][0] = 1;
}
//3.动态方程，从下到上，从左到右
for (int pre = num; pre >=1; pre--) {
//画图可知对角线下半区无效，所以rest从pre开始遍历
for (int rest = pre; rest <=num ; rest++) {
for (int i = pre; i <= rest; i++) {
dp[pre][rest] += dp[i][rest - i];
}
}
}
//4.返回结果
return dp[1][num];
}
斜率优化：
思路：通过画表观察dp[pre][rest]的周围的几个位置的依赖关系，找规律
例如：发现dp[pre+1][rest]的依赖的位置 和 dp[pre][rest] 依赖的位置在一条线上有重合部分，
整理重新得出：dp[pre][rest] = dp[pre+1][rest] + dp[pre][rest-pre]
这样可以替代掉for (int i = pre; i <= rest; i++)的循环，从而实现优化。
private int processDpUpgrade(int num){
//1.问题定义
//dp[pre][rest], 剩余rest需要刚好裂开(且上一个裂开的数据是pre)的方法数
//rest: 0~num, 大小为num + 1, pre: 1~rest, 大小：num + 1
int [][]dp = new int[num + 1][num + 1];
//2.边界
for (int pre = 0; pre <= num; pre++) {
dp[pre][0] = 1;
}
//分析可知，对角线为1
for (int pre = 0; pre <= num; pre++) {
dp[pre][pre] = 1;
}
//3.动态方程，从下到上，从左到右
for (int pre = num; pre >=1; pre--) {
//画图可知对角线下半区无效，所以rest从pre+1开始遍历
for (int rest = pre + 1; rest <=num ; rest++) {
//0(n)优化为了o(1)
dp[pre][rest] = dp[pre+1][rest] + dp[pre][rest-pre];
}
}
//4.返回结果
return dp[1][num];
}
