从递归到一维动态规划的理解
动态规划是一种通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而解决复杂问题的算法策略。一维动态规划是动态规划中较为基础的一类，它通常只需要一个一维数组来保存子问题的解。我们可以从递归的角度逐步引出一维动态规划。
递归的基本概念
递归是指在函数的定义中使用函数自身的方法。在解决问题时，递归通常将大问题分解为形式相同的小问题，直到达到最小的、可以直接求解的子问题（即递归的终止条件）。不过，递归可能会存在大量的重复计算，导致时间复杂度很高。
以斐波那契数列为例理解从递归到一维动态规划的转变步骤
1. 递归实现斐波那契数列
斐波那契数列的定义为：(F(n) = F(n - 1)+F(n - 2))，其中 (F(0)=0，(F(1)=1。
public static int fib1(int n) {return f1(n);}public static int f1(int i) {if (i == 0) {return 0;}if (i == 1) {return 1;}return f1(i - 1) + f1(i - 2);}递归的问题：在计算 F(n) 时，会多次重复计算 F(n - 1)、F(n - 2) 等子问题。例如，计算 F(5) 时，(F(3) 会被多次计算，这会导致时间复杂度呈指数级增长，为 O(2^n)。
2. 记忆化搜索实现斐波那契数列（自顶向下动态规划）
为了避免递归中的重复计算，我们可以使用一维数组来保存已经计算过的子问题的解，遇到时直接返回。
public static int fib2(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, -1);return f2(n, dp);}public static int f2(int i, int[] dp) {if (i == 0) {return 0;}if (i == 1) {return 1;}if (dp[i] != -1) {return dp[i];}int ans = f2(i - 1, dp) + f2(i - 2, dp);dp[i] = ans;return ans;}3. 严格位置依赖实现斐波那契数列（自底向上动态规划）
是利用数列项间严格位置依赖关系，从最小子问题起按序计算，避免递归重复计算以提升效率，让代码更易读且有空间优化潜力。
public static int fib3(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}int[] dp = new int[n + 1];dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}4. 用有限几个变量优化空间
为了简化代码。
public static int fib4(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}int lastLast = 0, last = 1;for (int i = 2, cur; i <= n; i++) {cur = lastLast + last;lastLast = last;last = cur;}return last;}相应题目链接
509. 斐波那契数 - 力扣（LeetCode）
983. 最低票价 - 力扣（LeetCode）
91. 解码方法 - 力扣（LeetCode）
639. 解码方法 II - 力扣（LeetCode）
264. 丑数 II - 力扣（LeetCode）
32. 最长有效括号 - 力扣（LeetCode）
467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）
940. 不同的子序列 II - 力扣（LeetCode）
