算法_动态规划_hdu2021_找零问题

今天在杭电刷题时，遇到了如下一题。

TIM截图20191218211343.png

一看，咦，这不是俺学过的找零问题吗？书上说的是用动态规划，nice，马上开干！

动态规划的代码如下

import java.util.Scanner;

public class hdu2021_发工资咯_动态规划 {
    public static void main(String[] args) {
        int[] coinKinds = {1, 2, 5, 10, 50, 100}; // 有序的币值数组
        
        Scanner sc = new Scanner(System.in);
        
        while(sc.hasNext()) {
            int teacherNum = sc.nextInt(); // 教师人数
            
            if(teacherNum == 0)
                break;
            
            int coinNum = 0; // 钱币最少数
            for(int i = 0; i < teacherNum; i++) {   
                int salary = sc.nextInt(); // 每个老师的工资
                coinNum += changeMaking(coinKinds, salary); // 每个老师工资的钱币最少数
            }
            
            System.out.println(coinNum);// 输出结果
        }
        sc.close();
    }
    
    public static int changeMaking(int[] coinKinds, int salary) {
        int[] result = new int[salary + 1]; //存储动态规划结果集的数组，长度为结算工资 + 1
        
        result[0] = 0; //结算工资为零时，钱币数为零
        
        /**
         * 动态规划求解
         * 1. 遍历结算工资从1——>salary
         * 2. while循环求出i - coinKinds[j]即当前结算金额 - 币值的所有钱币数数组中的最小钱币数
         * 3. temp初始化为结算工资+1，这样保证while循环中永远得到的是最小值。因为不会存在result[i - coinKinds[j]]大于temp初始化值的情况。
         * 4. 当结算工资遍历到=salary时，则求出了result[salary]的最小钱币数
         */
        for(int i = 1; i < salary + 1; i++) {
            int temp = salary + 1, j = 0;
            while(j < coinKinds.length && i >= coinKinds[j]) {
                temp = result[i - coinKinds[j]] > temp? temp: result[i - coinKinds[j]];
                j++;
            }
            result[i] = temp + 1;
        }
        return result[result.length - 1];
    }
}

但，当自己喜形于色地点开讨论一看！

天！深刻让我理解到了——解决同一问题的算法很多，但其效率和复杂程度却不一而同。

这句话的真谛

讨论中的代码如下：

image.png

啊，是真的很贪心啊！

但是，为毛还有更"贪心"的解法！

让我产生不想活下去的想法的解法：

image.png

大佬个屁，哎，话不多说，给跪了。