流殃

动态规划

发布于

了解一下

零钱兑换

题目

image-20210613100037414

答案

    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函数/数组的定义。自定向下

备忘录