侧边栏壁纸
博主头像
流殃博主等级

用微笑面对生活

  • 累计撰写 176 篇文章
  • 累计创建 43 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

动态规划

流殃
2021-06-12 / 0 评论 / 0 点赞 / 113 阅读 / 263 字 / 正在检测是否收录...

零钱兑换

题目

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

备忘录

0

评论区