数据结构与算法实例详解--动态规划/记忆化搜索

         动态规划和记忆化搜索都是用来解决最优问题的有效技术，特别适用于具有重叠子问题和最优子结构性质的问题。

        动态规划是一种自底向上的方法，它通过将大问题拆分成小问题，先解决这些小问题，并将结果存储到表中，以避免重复计算。这种方法通常使用迭代的方式，从最小的子问题开始逐步构建到最终的问题，其典型的应用场景包括 Fibonacci 数列、最短路径问题和背包问题等。

        记忆化搜索则是一种自顶向下的策略，它在递归的过程中使用一个数据结构（如字典或数组）来存储已经计算过的结果。每次在计算某个子问题时，首先检查该子问题的结果是否已经存在，若存在则直接返回，从而避免重复计算。记忆化搜索在实现上更直观，通常用于递归的场景，例如在求解组合数学问题时。

下面直接上实例：

494.目标和【中等】
题目：
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1
提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
分析问题：
设 nums 的元素和为 s，添加正号的元素之和为 p，添加负号的元素（绝对值）之和为 q，那么有

p+q=s
p-q=target
化简得：

p = (s+target) / 2 
q = (s-target) / 2
        我们找所有元素里面选取出来的元素和恰好为p的方案个数，那么这就变成了一道经典的0-1背包问题的变形，找恰好装capacity,求方案数/最大/最小价值和，capacity指的是容量，也就是这里的负数的和的绝对值。

        那么我们就可以根据传统的0-1背包问题的求解过程来解题，带上cache数组以便达到记忆化的一个效果。

此处也可以进行进一步的优化，用一个二维数组f来替代递推函数dfs：

        首先创建一个二维数组f，其中n表示数组的长度，target表示目标值，该数组用于记录不同状态下的结果。

        然后将f[0][0]初始化为1，这是一个基础的起始条件。接下来通过两个嵌套循环进行计算。外层循环遍历一个名为nums的数组，其中的每个元素x代表物品的价值。内层循环遍历目标值target的所有可能取值。在循环内部，根据不同条件更新f数组的值。

        如果c小于x，说明当前考虑的物品价值x大于当前的目标值c，无法选择该物品，所以f[i + 1][c]保持与f[i][c]相同。
        如果c大于或等于x，那么f[i + 1][c]等于f[i][c]加上f[i][c - x]，这表示在这种情况下，可以选择该物品，所以要将不选择该物品的情况（f[i][c]）和选择该物品的情况（f[i][c - x]）的结果相加。
        最后，函数返回f[n][target]，即最终在考虑了所有物品和目标值的情况下的结果。

代码实现：

优化前：

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        # p = (s+t) /2
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target //=2
        n=len(nums)
        @cache  # 保存记忆
        def dfs(i,c): # i是剩余多少个物品没装      c是当前背包剩余容量
            if i<0:
                return 1 if c==0 else 0
            if c < nums[i]:
                return dfs(i-1,c)
            return dfs(i-1,c)+dfs(i-1,c-nums[i])
        return dfs(n-1,target)

优化后:

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        # p = (s+t) /2
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target //=2
        n=len(nums)
 
        f=[[0]*(target+1) for _ in range(n+1)]
        f[0][0]=1
        for i,x in enumerate(nums):
            for c in range(target+1):
                if c<x: f[i+1][c] = f[i][c]
                else: f[i+1][c] = f[i][c] + f[i][c-x]
        return f[n][target]

总结：
优化后代码详细解释：
target += sum(nums)：将target值加上数组nums的元素总和，得到p的2倍。
if target < 0 or target % 2:：检查新的target值是否小于0或是否为奇数。如果是，则直接返回0，表示无法得到目标值。
target //= 2：将target值除以2，得到用于后续计算的新值。
n = len(nums)：获取数组nums的长度。
f = [[0] * (target + 1) for _ in range(n + 1)]：创建一个二维数组f，用于动态规划的计算。
f[0][0] = 1：设置初始状态，即当没有元素且目标值为0时，有一种方法可以达到。
通过两个嵌套循环进行动态规划计算：
外层循环for i, x in enumerate(nums):遍历数组nums的每个元素。
内层循环for c in range(target + 1):遍历所有可能的目标值。
在循环内部，根据当前元素x和目标值c的关系更新f[i + 1][c]的值。如果c < x，则f[i + 1][c] = f[i][c]，表示无法选择当前元素来达到目标值；如果c >= x，则f[i + 1][c] = f[i][c] + f[i][c - x]，表示可以选择或不选择当前元素来达到目标值，将两种情况的方法数相加。
最后，函数返回f[n][target]，即使用整个数组nums达到最终目标值的方法数。
考点：
动态规划的应用：通过构建二维数组来记录不同状态下的结果，根据状态转移方程进行计算。
对问题的数学转化：将原问题转化为通过加减运算得到特定值的问题，并进行了一些预处理和条件判断。
收获：
深入理解了动态规划的思想和应用方法，学会如何根据问题的特点构建合适的状态和状态转移方程。
提高了对问题进行数学分析和转化的能力，能够将复杂的问题简化为可计算的形式。
增强了对数组操作和循环的熟练程度，能够灵活运用这些基本编程技巧来解决实际问题。