想找个最简单的动态归划上上手，于是找到这个个人觉得最典型的动态归划问题：硬币找零问题

给一些不同面值的硬币，其中=1，以及数值M。要计算出找M所需要的最少硬币数。

比如我们有硬币<1,5,10,20>，那么如果要找33块钱的话，最少的零钱数是20+10+1+1+1，一共5个硬币。这就是硬币找零问题的简介。

下面给出几种解法：

1. 穷举法，这种方法虽然比较笨，但在规模较小的时候，也能够解决问题

   <?php
   function coin(){
   	$n = 9;
   	$m = 3;
   
   	$sum = 0;
   	$log = [];
   	for($i=0; $i<=$n; $i++){
   		for($j=0; $j<=$n; $j++){
   			for($k=0; $k<=$n; $k++){
   				$temp = $i+2*$j+3*$k;
   				if(($sum ==0 || $sum>$temp) && $temp==$n){
   					$sum = $i+$j+$k;
   					$log = [$i, $j, $k];
   				}
   			}
   		}
   	}
   
   	echo $sum;
   
   	echo '<br>';
   	echo "<pre>";
   	var_dump($log);
   	echo "</pre>";
   }
   

    

2. 贪婪法，这里要注意贪婪法会存在一些问题，要注意优化，尤其是是否能够找出最优解

   function coin1(){
   	$n = 9;
   	$m = [7, 3];
   
   	$sum = 0;
   	$log = [];
   
   	foreach($m as $i){
   		while($n>=$i){
   			$n -= $i;
   			$log[] = $i;
   			$sum ++;
   			if($n<$i) break;
   		}
   
   	}
   
   	echo $sum;
   
   	echo '<br>';
   	echo "<pre>";
   	var_dump($log);
   	echo "</pre>";
   }
   

    

3. 动态规划法， 这里要注意缓存，可以定义个数组来进行优化，缓存已经做过计算的值

   function coin2($n){
   	$m = [1, 2, 3];
   	$sum = 0;
   
   	if($n>1){
   		for($i=1; $i<count($m); $i++){
   			if($n>=$m[$i-1]){
   				$sum = min(coin2($n-$m[$i-1])+1, coin2($n-$m[$i])+1);
   			}
   		}
   	}
   
   	if($n==0){
   		$sum = 0;
   	}
   
   	if($n == 1){
   		$sum = 1;
   	}
   	return $sum;
   }
   
   echo coin2(9);
   

   这里给一个特别优秀全面的分析：

   若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

   用O(n)表示找n块所需最少的硬币数。这里可以看到，如果有硬币<1,3,4>，当想要求6块多需要的最少硬币数时O(6) = min{O(5)+1, O(3)+1, O(2)+1}。即我们想要找6块钱，我们只需要找出6-1=5，6-3=3，6-4=2这三种情况哪一种所需硬币数最少即可。因为我们只要在这三个数上加1即可。

   我们可以总结出对于硬币集合，想要找M块钱，则O(M) = min{O(M-a0)+1,……O(M-an)+1}.

   因此动态规划的伪代码如下。

   DP_coin_change(<a0,a1,...an>,M)
     coin_num <- Recurse_coin_change(<a0,a1,...an,M>)
     return coin_num
    
     Re_coin_change(<a0,a1,...an>,M>)
     if M < 0   return error 
     if M = 0   return 0
     if M = 1   return 1
     coin_num <- min{Re_coin_change(<a0,a1,...an>,M-a0)+1, Re_coin_change(<a0,a1,...an>,M-a1)+1,...Re_coin_change(<a0,a1,...an>,M-an+1)}
     return coin_num

   总的来说，动态归划的难点在于找通项公式，这个问题比较好找，有的问题会比较难找，需要大家不断提升。

转载请注明：朋克网 » 最小白的动态归划入门（硬币找零问题）