动态规划

函数式的动态规划 动态规划是一类很常用的算法，在C/C++/Java中一般使用于数组进行记忆化。而函数式编程语言一般无法方便地操作数组这些依赖副作用的数据结构，函数式的记忆化便要另寻他法。 本文就是一个简单的笔记，用一些代码片段展示我所知的函数式动态规划的技巧。 （2020/5/17，时隔五个月后的更新，新增Memocombinators） Course-of-Values Recursion Course-of-Values Recursion是我认为最直观的一种技巧，就是将遍历过的结果当作返回值的一部分保留下来，在递归的时候可以取得运算过的值。 对于递归函数f，定义一个辅助的函数bar $\begin{align} \overline{f}(n) = [f(n), f(n-1),...,f(0)] \end{align}$ 则原递归函数f可以用bar表示出来： $head(\overline{f}(n))$ 斐波那契数列： fibBar :: Int -> [Int] fibBar 0 = [0] fibBar 1 = 1:fibBar 0 fibBar n = let course = fibBar (n-1) in -- [fib(n-1)..fib(0)] let p = course !! 0 in -- fib(n-1) let pp = course !! 1 in -- fib(n-2) p + pp : course -- >>> fibBar 10 -- [55,34,21,13,8,5,3,2,1,1,0] -- Binary Partitions：...