在Java中，动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为子问题并存储子问题解来避免重复计算的高效算法策略，其核心思想是“记忆化”与“状态转移”，适用于具有重叠子问题和最优子结构特性的问题，本文将从DP的基本概念、实现步骤、经典案例及优化技巧等方面,详细阐述DP在Java中的计算方法。
动态规划的核心思想
动态规划的本质是将原问题分解为若干个相互关联的子问题，通过求解子问题的解来构建原问题的解，与分治算法不同，DP会存储子问题的解，避免重复计算，从而将指数级复杂度降低至多项式级，实现DP的关键在于两个要素：
- 最优子结构：问题的最优解包含子问题的最优解，例如斐波那契数列的第n项依赖于前两项的最优解。
- 重叠子问题：子问题会被重复计算，例如计算斐波那契数列时，
fib(5)需要计算fib(4)和fib(3)，而fib(4)又会涉及fib(3)，此时fib(3)被重复计算。
动态规划的两种实现方式
在Java中，DP通常通过两种方式实现：自顶向下（记忆化搜索）和自底向上（递推）。
自顶向下（记忆化搜索）
自顶向下的方法采用递归思想，从原问题出发，递归求解子问题，并通过缓存（如数组或哈希表）存储已计算的子问题解，避免重复计算。
实现步骤：
- 定义递归函数，明确状态参数（如子问题的规模）。
- 初始化缓存数组，标记未计算的子问题（通常用-1或特殊值）。
- 在递归函数中，先检查缓存，若已计算则直接返回；否则递归计算并存入缓存。
示例代码（斐波那契数列）：
public class Fibonacci {
private static int[] memo; // 缓存数组
public static int fib(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1); // 初始化为-1，表示未计算
memo[0] = 0;
memo[1] = 1;
return helper(n);
}
private static int helper(int n) {
if (memo[n] != -1) return memo[n]; // 已计算，直接返回
memo[n] = helper(n - 1) + helper(n - 2); // 递归计算并缓存
return memo[n];
}
}
自底向上（递推）
自底向上的方法通过迭代从最小子问题开始，逐步求解更大的子问题，直至原问题，其核心是定义状态转移方程，并按顺序填充DP表（如数组）。
实现步骤：
- 确定DP数组的定义，明确
dp[i]表示的含义（如第i个子问题的解）。 - 初始化DP数组的边界条件（如
dp[0]、dp[1]）。 - 根据状态转移方程，从初始状态开始迭代填充DP数组。
示例代码（斐波那契数列）：
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
}
return dp[n];
}
}
动态规划的经典应用场景
DP在算法竞赛和实际开发中应用广泛，以下列举几个经典问题：
0-1背包问题
问题描述：给定N个物品和一个容量为C的背包，每个物品有重量w[i]和价值v[i]，求装入背包的最大价值。
DP思路：定义dp[i][j]表示前i个物品在容量为j时的最大价值，状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) // 装入第i个物品或不装入优化：可将二维数组优化为一维数组，通过倒序迭代节省空间。
最长公共子序列（LCS）
问题描述：求两个字符串的最长公共子序列长度。
DP思路：定义dp[i][j]表示字符串A的前i个字符与字符串B的前j个字符的LCS长度，状态转移方程为：
if (A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);最小路径和
问题描述：给定一个m×n的网格，每个格子有一个非负数，求从左上角到右下角的最小路径和（每次只能向右或向下移动）。
DP思路：定义dp[i][j]表示到达格子(i,j)的最小路径和，状态转移方程为：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]); // 从上方或左方转移动态规划的优化技巧
- 空间优化：对于状态转移仅依赖前几项的问题（如斐波那契数列、背包问题），可将DP数组从二维降为一维，甚至用变量滚动计算，节省空间。
- 状态压缩：当DP状态涉及多个维度且维度较小时，可通过位运算或哈希表压缩状态表示，减少内存占用。
- 预处理与边界条件：明确DP数组的边界条件（如
dp[0]、dp[1]），避免数组越界或逻辑错误。
动态规划是解决复杂问题的利器，其核心在于“分解问题、存储子解、递推求解”，在Java中，无论是自顶向下的记忆化搜索，还是自底向上的递推，关键在于定义清晰的状态转移方程和合理的DP表设计，通过经典问题的实践和优化技巧的运用，可以逐步掌握DP的精髓,高效解决各类算法问题。
