使用函数式编程解决动态编程问题(第3部分)
在上一篇文章中,我们看到了一种功能上解决背包问题的方法。 当解决方案之间的依赖关系具有其他形状时,我们可以做同样的事情吗? 例如,在该项目的Euler问题中,解决方案彼此不同。 再一次,让我们从问题定义开始,该定义使我们可以将问题分解为子问题: 让我们考虑一些位置(i,j) 。 要到达该位置,我们只有两种可能性:要么通过从上排到达然后从该位置下降到该位置,要么从上一列进入并从那里开始。 这两种可能性是互斥的,因此我们可以计算它们之间的最小值以计算(i,j)的最优解: 这里v(i,j)是存储在第i行和第j列的值。 再一次,让我们画一个图显示依赖关系: 这里的基本案例有一个重要的区别。 第一行中每个值的最小路径就是从(0,0)开始并从此处开始的路径(这是公式R(i,j),它是累积行总和)。 类似地,第一列中每个值的最小路径是从此处开始并从此处向下的部分(这是公式C(i,j) ,它是累积列总和)。 现在,与0/1背包问题不同, (i,j)的解决方案不仅取决于上一行的值。 它还取决于同一行中的先前值。 让我们从基本情况开始:如何计算数字数组的累加和?…