Journal InTime


2011-12-23 (Fri) [長年日記]

_ Arrayで動的計画法

Haskellではデータがimmutableなので動的計画法はどうやるんだろうと思ったが、Arrayですっきり書けるようだ。

試しにグリッド上の経路の数を計算してみる。

import Data.Array

routeCount :: Int -> Int -> Integer
routeCount width height =
  routes ! (width, height)
    where routes = array ((0, 0), (width, height)) $
            -- 一番下の行の経路数はすべて1
            [ ((x, 0), 1) | x <- [0..width] ] ++
            -- 一番左の列の経路数はすべて1
            [ ((0, y), 1) | y <- [1..height] ] ++
            -- 残りは、左と下の点までの経路数の和
            [ ((x, y), routes ! (x - 1, y) + routes ! (x, y - 1))
              | x <- [1..width], y <- [1..height] ]

main = print $ routeCount 5 4

遅延評価のおかげで、routesの定義中でroutesを再帰的に参照できる。かっこいい。

Tags: Haskell