在前面的动态规划系列文章中，关于如何对递归进行分析的四种基本模型都介绍完了，再来回顾一下：
- 从左到右模型 ：
arr[index ...]从index之前的不用考虑，只考虑后面的该如何选择 。 - 范围尝试模型 ：思考
[L ,R]两端，即 开头和结尾 处分别该如何取舍。 - 样本对应模型 ：以 结尾位置 为出发点，思考两个样本的结尾都会产生哪些可能性 。
- 业务限制模型 ：不能够明确的知道一个参数的变化范围，通过业务的限制找到 最差情况 进行估计。
今天我们通过最熟悉的 从左到右模型 继续学习 消除枚举行为 的 斜率优化问题 。
整数 N 的裂开Ⅰ
给定一个正整数 N ，求把 N 裂开的方法数有多少种，要求后面的数不能小于前面的数。
示例 1：
输入： N = 4
输出： 5
解释： 共 5 种裂开方式
- 1, 1, 1, 1
- 1, 1, 2
- 1, 3
- 2, 2
- 4
首先我们依然采用最朴素的 暴力递归 来思考这道题目。
思路
这道题就是典型的 从左到右模型 ，因此，递归就可以按照: 当前来到的位置之前的不用考虑，只考虑后面的该如何选择 的方式思考。
唯一的限制条件就是不能比前一个数小，因此，我们需要用变量记录 前面的数 是几，以及 后面还剩几 可以给我们裂开。
代码
public static int ways(int n) {if (n <= 0) {return 0;}if (n == 1) {return 1;}return process(1, n);
}public static int process(int pre, int rest) {if (rest == 0) {return 1;}if (pre > rest) {return 0;}int ways = 0;// 保证不小于前一个数for (int one = pre; one <= rest; one++) {ways += process(one, rest - one);}return ways;
}
代码解释
递归中的 base case ，如果当前剩余的数为 0 了，说明前面的组合刚好满足题意，裂完了，记为有效的一种情况。
若上一轮裂开之后，剩余的数字已经小于了 pre ，说明已经没有可以方案了，直接返回 0 。
因为不能比前一个数小，因此直接从上一个数字开始依次增大且不超过剩余值即可。
下面我们通过画 dp 表，探寻如何修改出动态规划版本。
假设 n = 5 。
由递归可知，当 rest 为 0 时，返回 1。另外，当 pre == rest 可以知道，只剩下一种裂开方式，即 rest 作为最后一个数字，不能再裂开了。
- 例如： pre=2, rest=2。此时的裂开方式只能为 2, 2 。
因此，对角线均为 1 。
当 pre > rest 时，无结果，返回 0 。
对于一般位置，process(one, rest - one) 中 one 的值逐渐增大，rest-one 的值逐渐减小。即依赖左下的位置：
动态规划版
public static int dp(int n) {if (n <= 0) {return 0;}if (n == 1) {return 1;}int[][] dp = new int[n + 1][n + 1];// 为初始化for (int pre = 1; pre <= n; pre++) {dp[pre][0] = 1;dp[pre][pre] = 1;}// 初始化完毕，倒着填表for (int pre = n - 1; pre >= 1; pre--) {for (int rest = pre + 1; rest <= n; rest++) {int ways = 0;for (int one = pre; one <= rest; one++) {ways += dp[one][rest - one];}dp[pre][rest] = ways;}}// 返回右上角的值return dp[1][n];
}
代码解释
可变的参数有两个：前一个数 pre 和 剩余数 rest 。因此，需要设置一个二维的 dp 表数组，由于 pre, rest 的取值范围均为 0~n ，因此数组大小设置为 dp[n + 1][n + 1] 。第一列和对角线均为 1 。
由上面的例子分析可知，普遍位置依赖左下位置的值，因此可以倒着从下往上，从左到右填写 dp 表。
根据递归调用 process(1, n) 可知最终返回 dp[1][n] 。
观察递归的代码，发现竟然有 3 层 for 循环。为什么呢？
思考后发现， dp 表中的每个位置同样需要 枚举 后才能知道。那有没有办法消掉这层枚举的 for 循环呢？答案是有的！
下面我们继续观察 dp 表，探寻该动态规划应如何进一步优化。
假设此时 pre=2，rest=5（虽然这种情况在 n=5 时不会发生）。
一图胜千言~
由图可知，dp[2][5] 的值，红色 = 蓝色 + 3 个黄色 。
蓝色：把 5 裂开一个 2 后，rest=3 。（蓝行 = 红行，蓝列 = 红列 - 红行）。
黄色：裂开 3 剩 2；裂开 4 剩 1；裂开 5 剩 0。
观察发现，紫色 = 3 个黄色 。
因此，替换一下：红色 = 蓝色 + 紫色 。这样就消除了枚举的 for 循环。
最终优化版动态规划
public static int dp(int n) {if (n <= 0) {return 0;}if (n == 1) {return 1;}int[][] dp = new int[n + 1][n + 1];for (int pre = 1; pre <= n; pre++) {dp[pre][0] = 1;dp[pre][pre] = 1;}for (int pre = n - 1; pre >= 1; pre--) {for (int rest = pre + 1; rest <= n; rest++) {// 红色 = 紫色 + 蓝色dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];}}// 返回右上角return dp[1][n];
}
相信代码很容易看懂，这样就完成了最终版 斜率优化 后的动态规划~
前面学习的如何一步步的将暴力递归修改为严格表依赖动态规划的基础要打牢哦！还不会的赶快关注一下回顾前面的几篇文章吧！
~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！
------------- 往期回顾 -------------
所发博客文章大合集（实时更新）
【算法 - 动态规划】找零钱问题Ⅰ
【算法 - 动态规划】找零钱问题Ⅱ
【算法 - 动态规划】找零钱问题Ⅲ
【算法 - 动态规划】京东面试题 - 洗咖啡杯问题
【堆 - 专题】“加强堆” 解决 TopK 问题！
AC 此题，链表无敌！！！
