F#中的二维动态规划

Question

我需要在F#中实现一个简单的2D动态编程算法。对于简单的1D情况，Seq.unfold似乎是可行的，参见例如https://stackoverflow.com/a/7986083/5363

有没有一种很好(也很有效)的方法来在2D中达到类似的效果，比如用函数式重写下面的伪代码：

  let alpha = 
    let result = Array2D.zeroCreate N T
    for i in 0 .. N-1 do
      result.[0, i] <- (initialPi i) * (b i observations.[0])
    for t in 1 .. T-1 do
      for i in 0 .. N-1 do
        let s = row t-1 result |> Seq.mapi (fun j alpha_t_j -> alpha_t_j * initialA.[i, j]) () |> Seq.sum
        result.[t, i] <- s * (b i observations.[t])
    result 

假设上面定义了所有缺少的函数和数组。

Answer 1

编辑:实际阅读代码，这至少是功能性的，确实有一个稍微不同的返回类型，尽管您可以通过转换来避免这种情况

let alpha = 
    let rec build prev idx max = 
        match idx with
        |0 -> 
            let r = (Array.init N (fun i -> (initialPi y) * (b i observations.[0]))
            r:: (build r 1 max)
        |t when t=max -> []
        |_ ->  
             let s = prev |> Seq.mapi (fun j alpha_t_j -> alpha_t_j * initialA.[i, j]) () |> Seq.sum
             let r = Array.init N (fun i -> s * (b i observations.[t]))
         r:: build r (idx+1 max)
    build [] 0 T |> List.toArray