在有向无环图(DAG)中寻找总路径成本等于或尽可能接近目标值的路径

• 第一步：定义DP表含义：你可以用dp[i][s]作为布尔类型的状态，表示处理完前i层（对应前i个矩阵）时，是否可以得到总和为s的合法选择。如果有回溯路径的需求，可以把状态值改为存储当前层选择的元素/边的索引，仅求最值的话布尔类型足够。
• 第二步：初始化边界状态：处理第0层（对应第一个矩阵/最左侧出发层）时，遍历该层所有可选的边权值/矩阵元素值v，将所有dp[0][v]标记为True，仅保留小于等于目标值T的状态即可。
• 第三步：逐层填充DP表：遍历从第1层到最后一层的所有层，对每一层的状态计算仅依赖上一层的所有可达状态：遍历上一层所有标记为True的和值s_prev，再遍历当前层所有可选的边权/元素值v_curr，计算新和值s_new = s_prev + v_curr，如果s_new <= T，就将dp[i][s_new]标记为True。计算过程中可以对当前层的和值去重，避免重复计算相同状态。
• 第四步：查找最优结果：所有层的状态填充完成后，从目标值T开始从大到小遍历，找到第一个dp[总层数-1][s]为True的s，就是小于等于目标值的最接近解。
• 可选优化思路：因为计算第i层状态仅需要第i-1层的状态集合，不需要存储完整的二维DP表，仅用两个一维数组/集合分别存储上一层可达和、当前层可达和即可，可大幅降低空间占用。如果计算过程中某一层已经出现等于T的可达和，可以直接提前终止计算，该值就是最优解。

内容的提问来源于stack exchange，提问作者superstrayan