This array is for dynamic programming. You can diagonalize it into a list and use technique similar to the Fibonacci numbers.
The resulting solution should be purely declarative. 2012/12/11 mukesh tiwari <mukeshtiwari.ii...@gmail.com>: > Hello All > I am trying to transform this C++ code in Haskell. In case any one > interested this is solution of SPOJ problem. > > #include<cstdio> > #include<iostream> > #include<cstring> > using namespace std; > > int memo[1100][1100] ; > > int recurse( int h , int a , int cnt , bool flag ) > { > if ( h <= 0 || a <= 0 ) return cnt ; > if ( memo[h][a] ) return memo[h][a] ; > if ( flag ) memo[h][a] = recurse ( h + 3 , a + 2 , cnt + 1 , !flag ) > ; > else > memo[h][a] = max ( memo[h][a] , max ( recurse ( h - 5 , a - 10 , > cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ; > > return memo[h][a]; > } > > int main() > { > int n , a , b ; > scanf( "%d", &n ); > for(int i = 0 ; i < n ; i++) > { > memset ( memo , 0 , sizeof memo ) ; > scanf("%d%d", &a , &b ); > printf("%d\n" , recurse( a , b , -1 , 1 )); > if( i != ( n - 1 ) ) printf("\n"); > } > > } > > I am stuck with that memo[1100][1100] is global variable so I tried to solve > this problem using state monad ( Don't know if its correct approach or not ) > but it certainly does not seem correct to me. Till now I came up with code. > Could some one please tell me how to solve this kind of problem ( Generally > we have a global variable either multi dimensional array or map and we > store the best values found so far in the table ). > > import qualified Data.Map.Strict as SM > import Control.Monad.State > > {-- > funsolve_WF :: Int -> Int -> Int -> Int > funsolve_WF h a cnt > | h <= 0 || a <= 0 = cnt > | otherwise = funsolve_Air h a ( cnt + 1 ) > > funsolve_Air :: Int -> Int -> Int -> Int > funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' ) > ( funsolve_WF ( h + 3 - 20 ) ( a + 2 + 5 ) cnt' ) where > cnt' = cnt + 1 > --} > > > > funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int ) Int ) > Int > funSolve hl am cnt f > | hl <= 0 && am <= 0 = return cnt > | otherwise = do > mp <- get > case () of > _| SM.member ( hl , am ) mp -> return mp SM.! ( hl , am ) > | f -> do > --here I have to insert the value return by function > funSolve ( hl + 3 ) ( am + 2 ) ( cnt + 1 ) ( not f ) to map whose key is ( > hl , am ) > let k = evalState ( funSolve ( hl + 3 ) ( am + 2 ) > ( cnt + 1 ) ( not f ) ) mp > modify ( SM.insert ( hl , am ) k ) > > > | otherwise -> do > do > let k_1 = evalState ( funSolve ( hl - 5 ) ( am - 10 > ) ( cnt + 1 ) ( not f ) ) mp > k_2 = evalState ( funSolve ( hl - 20 ) ( am + 5 > ) ( cnt + 1 ) ( not f ) ) mp > k_3 = mp SM.! ( hl , am ) > modify ( SM.insert ( hl , am ) ( maximum [ k_1 , > k_2 , k_3 ] ) ) > > Regards > Mukesh Tiwari > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe