动态规划算法模板
public class DynamicProgramming {
public int solve(int n, int[] nums) {
// Step 1: 初始化 dp 数组，dp[i] 表示从0到i的最优解
int[] dp = new int[n + 1];
// Step 2: 设置初始条件，通常是dp数组的第一个元素
dp[0] = 0; // 假设从第0个元素开始
// Step 3: 遍历状态空间，求解每一个子问题
for (int i = 1; i <= n; i++) {
// Step 4: 使用递推公式更新 dp[i]
dp[i] = Math.max(dp[i-1], dp[i-1] + nums[i-1]);
}
// Step 5: 返回最终结果，通常是dp[n]，即最终问题的解
return dp[n];
}
}
1. 状态定义
状态定义是动态规划的基础，它决定了我们如何将一个问题分解为子问题，并通过子问题的解来推导出原问题的解。在动态规划中，状态通常通过一个数组（如dp）来表示。
具体说明：
dp[i]通常表示从起点到某个位置i的最优解（或最小值、最大值等，取决于问题的要求）。可以根据问题的需求来定义每个dp[i]的含义。- 在动态规划问题中，
i可以是数组的索引、图的节点、区间的边界、时间步等，具体取决于问题的模型。
示例：对于求解最大子数组和问题，dp[i]表示以位置i结尾的子数组的最大和。因此，dp[i]的计算不仅依赖于前一个元素，还可能取决于前面某个更远的位置。
一维数组 DP：
- 常见的例子包括斐波那契数列、爬楼梯问题、最短路径问题等。通过一个一维数组
dp来记录从0到n的中间结果。二维数组 DP：
- 适用于有二维状态空间的问题，如最长公共子序列、背包问题等。需要用二维数组
dp[i][j]来表示状态。
2. 边界条件
边界条件是动态规划算法中的起点，它确保在计算时能够从正确的初始状态出发。正确的边界条件可以确保算法的正确性，避免出现无效或不符合题意的计算。
具体说明：
- 边界条件通常是最基本的情况，它们的值是已知的。
- 在许多动态规划问题中，边界条件可能是
dp[0]、dp[1]等，它们的值通常由问题本身定义，确保算法能够顺利进行。
示例：对于最大子数组和问题，dp[0]通常是0，表示空数组的和为0。
3. 状态转移方程
状态转移方程是动态规划的核心，它定义了如何从已知的子问题结果推导出当前问题的解。在动态规划中，转移方程决定了我们如何使用dp[i-1]、dp[i-2]等之前的子问题结果来计算当前状态dp[i]。
具体说明：
- 状态转移方程的设计基于问题的性质，通常是通过选择、递归或叠加等方式推导出当前状态。
- 每个状态
dp[i]的值，通常由一个或多个之前的状态（如dp[i-1]、dp[i-2]）通过递推关系计算出来。
示例：对于最大子数组和问题，dp[i]的状态转移方程可以是：
dp[i] = max(dp[i-1] + nums[i], nums[i]);
这表示：如果前面的子数组和加上当前元素nums[i]大于当前元素nums[i]，则延续前面的子数组，否则从当前位置重新开始一个新的子数组。
示例：斐波那契数列
在斐波那契数列问题中，状态转移方程是dp[i] = dp[i - 1] + dp[i - 2]，表示当前的第i项由前两项的和推导而来。
public class Fibonacci {
public int fibonacci(int n) {
// 创建dp数组并初始化
int[] dp = new int[n + 1];
dp[0] = 0; // 斐波那契数列的起始值
dp[1] = 1; // 斐波那契数列的第二项
// 填充dp数组
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
}
// 返回结果
return dp[n];
}
public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.fibonacci(10)); // 输出斐波那契数列的第10项
}
}