递归与循环结合处理一维dp的核心是递归建模+循环/记忆化求值：用memo避免重复计算，或转为自底向上填表，兼顾清晰性与效率。
递归与循环结合处理一维数组的动态规划问题，核心在于：用递归定义状态转移逻辑，用循环（或记忆化）避免重复计算。这不是“递归+for嵌套”那么简单，而是分工明确——递归负责思维建模，循环（或数组迭代）负责高效求值。
用记忆化递归（Memoization）替代纯递归
纯递归容易超时，尤其面对一维DP常见场景（如爬楼梯、打家劫舍、最长递增子序列）。解决办法是加一个数组或HashMap缓存已算过的状态，让递归只算一次。
- 定义 dp[i] 表示从位置 i 出发能获得的最优解（比如最大收益、最少步数）
- 写递归函数 int solve(int i)，先查 memo[i] 是否有值，有就直接返回
- 否则按状态转移方程计算（比如 dp[i] = Math.max(solve(i+1), solve(i+2) + nums[i])），存入 memo[i] 再返回
- 主函数里调用 solve(0)，自动触发自顶向下计算
用循环实现自底向上填表（标准DP写法）
如果递归思路清晰，可直接转成循环：把 memo 数组变成 dp 数组，用 for 从边界开始正向填充。
- 确定 base case：比如 dp[n-1] = nums[n-1]，dp[n-2] = Math.max(nums[n-2], nums[n-1])
- 倒序遍历（i 从 n-3 到 0）或正序（视转移依赖而定），按相同转移式更新 dp[i]
- 避免递归调用开销，空间还可优化（如只保留 dp[i+1] 和 dp[i+2]）
- 例如打家劫舍：dp[i] = Math.max(dp[i+1], dp[i+2] + nums[i])，循环实现更简洁稳定
混合使用：递归定义 + 循环预处理/后处理
有些问题需要先用循环准备辅助信息，再用递归决策；或递归返回结构化结果，循环汇总。
- 比如“分割等和子集”可先用循环算出总和、目标值，再用递归+memo判断能否凑出 target
- 又如“数组拆分使乘积最大”，先用循环排序数组，再递归处理分组策略
- 关键点：循环做确定性预处理（排序、前缀和、可行性校验），递归专注带选择的状态空间搜索
注意栈溢出与状态设计边界
一维数组 DP 的递归深度等于数组长度，n > 10⁴ 时纯递归易栈溢出。务必配合 memo 或改用循环。
- 递归函数参数尽量精简：通常只需下标 i，避免传整个数组或大对象
- 状态定义要无后效性：dp[i] 只依赖 i 之后（或之前）有限几个状态，不能依赖全局变量
- 初始化 memo 数组时，用特殊值（如 -1）标记未计算，避免与合法结果（如 0）混淆
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
