动态规划

零钱兑换

题目

答案

    public static int change(int amount, int[] coins) {
        // 
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

如何列出正确的状态转移方程

1. 确定基础的例子
2. 确定【状态】，也就是原问题和子问题中会变化的变量
3. 确定【选择】，也就是导致【状态】产生变化的行为
4. 明确dp函数/数组的定义。自定向下

备忘录