题解 | #求平方根#

1.可以用贪心来一波，显然超时

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        if(arr.length == 0){
            return -1;
        }
        Arrays.sort(arr);
        int n = arr.length;
        int res = 0;
        outloop:
        for(int i = n - 1; i >=0; i--) {
            int temp = aim - arr[i];
            while(temp >= 0) {
                res++;
                aim = temp;
                if(temp == 0) break outloop;
            }
            
        }  
        return res;
    }
}

2.动态规划（正解）

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        int n = arr.length;
        if (aim < 1) {
            return 0;
        }
        int[] dp = new int[aim + 1];
        
        Arrays.fill(dp, aim + 1);
        dp[0] = 0;
        for (int i = 1; i <= aim; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= arr[j])
                    dp[i] = Math.min(dp[i - arr[j]] + 1, dp[i]);
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }
}