消除重复的计算 ■要消除重复计算,可在在计算过程中保存已解 决的子问题的答案。这样,每个子问题只计算 次,而在后面需要时只要简单查一下,从而 避免重复计算 计算方式可依据递归式自底向上地进行。 注意到在此问题中,不同的有序对(j)就对应 不同的子问题,因此不同的子问题个数个数最 多只有C2+n=0(n2)个。 这样便可以得到多项式时间的算法 算法设计与分析 9算法设计与分析 9 消除重复的计算 ◼ 要消除重复计算，可在在计算过程中保存已解 决的子问题的答案。这样，每个子问题只计算 一次，而在后面需要时只要简单查一下，从而 避免重复计算。 ◼ 计算方式可依据递归式自底向上地进行。 ◼ 注意到在此问题中，不同的有序对 (i, j)就对应 不同的子问题，因此不同的子问题个数个数最 多只有Cn 2+ n = (n 2 )个。 ◼ 这样便可以得到多项式时间的算法