17370845950

Java动态规划是求解最优化问题的思想，核心为三步：定义状态、写状态转移方程、确定初始值与计算顺序，依赖最优子结构和重叠子问题两大特征。

Java 动态规划是一种用代码实现的**最优化问题求解思想**，不是某个固定函数或类，而是把大问题拆成有依赖关系的小问题，边算边记、避免重复，最终推出最优解的策略。

它解决的是这类问题

比如：爬楼梯（多少种走法）、背包里装什么最值钱、字符串怎么编辑最省操作、路径怎么走最短……这些题都有两个关键特征：

• 最优子结构：整体最优解，一定由某个子问题的最优解拼出来
• 重叠子问题：不同分支会反复算同一个子问题（比如 f(3) 在算 f(5) 和 f(4) 时都被用到）

Java 里怎么做动态规划

核心是三步走，用数组（或 HashMap）存中间结果：

• 定义状态：比如 dp[i] 表示“走到第 i 级楼梯的方法数”
• 写出状态转移方程：比如 dp[i] = dp[i-1] + dp[i-2]（只能跨 1 或 2 步）
• 确定初始值和计算顺序：dp[0]=1, dp[1]=1，然后从小到大填表

和递归、分治、贪心的区别

递归不存结果，容易超时；分治的子问题互相独立，而动态规划的子问题层层依赖；贪心只看眼前一步最优，动态规划会综合前面所有可能路径再选最优。

基本上就这些。写 Java DP 题，重点不在语法，而在想清楚“状态怎么设”和“怎么从已知推未知”。