20200904找零钱（贪心、动态规划）

一、贪心

import java.util.Arrays; public class 零钱兑换 { //假设有25分、10分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少 public static void main(String[] args) { Integer[] money ={25,20,5,1}; int M=41; Arrays.sort(money,(Integer o1,Integer o2)->{return o2-o1;});//o2-o1>0交换为降序 int coins=0; for(int i=0;i<money.length;i++){ if(M<money[i]){ continue; } System.out.println(money[i]); M -=money[i]; coins++; i=0; } System.out.println(coins); } }

二、动态规划

 

static int coins3(int n){ if(n<1) return -1; int[] dp=new int[n+1];//当前所需最小硬币数量 dp[0]=0; dp[1]=1; for(int i=1;i<=n;i++){ // dp[n]=Math.min(dp[n-25], dp[]); int min=0; if(i>=1)min=Math.min(dp[i-1],min); if(i>=5)min=Math.min(dp[i-5],min); if(i>=20)min=Math.min(dp[i-20],min); if(i>=25)min=Math.min(dp[i-25],min); dp[i]=min+1; } return dp[n]; }