记忆化递归将斐波那契时间复杂度降至o(n)；数组填充法用迭代实现o(1)空间；0-1背包一维dp压缩空间；二维dp显式建模便于理解；回溯法还原最优物品组合。
一、使用记忆化递归求解斐波那契数列
斐波那契数列存在大量重复子问题，直接递归会导致指数级时间开销。引入字典缓存已计算结果，可将时间复杂度降至线性级别。
1、定义静态字典 private static readonly Dictionary
2、编写递归方法，在每次返回前检查键是否存在，若存在则直接返回值；否则计算后存入字典并返回。
3、在方法入口处添加判断：if (memo.ContainsKey(n)) return memo[n];
4、对 n == 0 和 n == 1 的情况分别返回 0 和 1，并在计算 result = Fib(n-1) + Fib(n-2) 后执行 memo[n] = result;
二、采用自底向上数组填充法求解斐波那契数列
该方法规避递归调用栈开销，通过迭代方式从小到大依次计算每个斐波那契数值，仅需常数空间即可完成。
1、声明长度为 n+1 的 long 类型数组 dp = new long[n + 1];
2、初始化 dp[0] = 0，dp[1] = 1（若 n ≥ 1）。
3、使用 for 循环从 i = 2 到 i ≤ n，执行 dp[i] = dp[i - 1] + dp[i - 2];
4、返回 dp[n] 作为最终结果。
三、实现 0-1 背包问题的一维动态规划解法
利用滚动数组思想压缩空间，将二维状态转移降为一维，避免创建完整二维表，显著节省内存占用。
1、声明长度为 capacity + 1 的整型数组 dp = new int[capacity + 1];
2、外层遍历所有物品索引 i，内层从 capacity 递减至当前物品重量 weight[i]。
3、在内层循环中更新：dp[w] = Math.Max(dp[w], dp[w - weight[i]] + value[i]);
4、确保每次更新不依赖本轮已被覆盖的较小下标值，从而维持状态有效性。
四、使用二维数组显式建模背包问题的状态转移
通过构建 rows = items.Length + 1、cols = capacity + 1 的二维数组，清晰呈现每一步决策过程，便于调试与理解。
1、初始化二维整型数组 dp = new int[items.Length + 1, capacity + 1];
2、外层循环 i 从 1 到 items.Length，内层循环 w 从 0 到 capacity。
3、若当前物品重量大于 w，则 dp[i, w] = dp[i - 1, w];
4、否则取两种选择的最大值：dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weight[i - 1]] + value[i - 1]);
五、应用递归回溯结合备忘录输出背包最优解的具体物品组合
在完成动态规划填表后，通过反向追踪 dp 表格路径，识别哪些物品被选中，还原出实际选取方案。
1、从位置 (items.Length, capacity) 开始回溯，设置空列表用于收集索引。
2、若 dp[i, w] != dp[i - 1, w]，说明第 i-1 个物品被选中，将其加入列表，并令 w -= weight[i - 1]。
3、无论是否选取，均执行 i-- 继续上一行比较。
4、当 i == 0 或 w == 0 时终止，返回逆序后的物品索引列表。
