how to optimise this code?

[aalas]

I have a solution to the below problem in PHP. But it is taking too much time to execute for 10 digit numbers. I want to know where am I going wrong ?I am new to dynamic programming .Can someone have a look at this ?ProblemIn Byteland they have a very strange monetary system.Each Bytelandian gold coin has an integer number written on it. A coin ncan be exchanged in a bank into three coins: n/2, n/3 and n/4.But these numbers are all rounded down (the banks have to make a profit).You can also sell Bytelandian coins for American dollars. The exchangerate is 1:1. But you can not buy Bytelandian coins.You have one gold coin. What is the maximum amount of American dollarsyou can get for it?========================================================\[code\]<?php $maxA=array();function exchange($money){ if($money == 0) { return $money; } if(isset($maxA[$money])) { $temp = $maxA[$money]; // gets the maximum dollars for N } else { $temp = 0; } if($temp == 0) { $m = $money/2; $m = floor($m); $o = $money/3; $o = floor($o); $n = $money/4; $n = floor($n); $total = $m+$n+$o; if(isset($maxA[$m])) { $m = $maxA[$m]; } else { $m = exchange($m); } if(isset($maxA[$n])) { $n = $maxA[$n]; } else { $n = exchange($n); } if(isset($maxA[$o])) { $o = $maxA[$o]; } else { $o = exchange($o); } $temp = max($total,$m+$n+$o,$money); $maxA[$money]=$temp; //store the value }return $temp; }$A=array();while(1){ $handle = fopen ("php://stdin","r"); $line = fgets($handle); if(feof($handle)) { break; } array_push($A,trim($line));}$count =count($A);for($i=0;$i<$count;$i++){ $val = exchange($A[$i]); print "$val \n"; }?>\[/code\]