动态规划

Posted on 2021-06-12 Edited on 2025-04-08 Views: Waline:

了解一下

零钱兑换

题目

答案


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];

}

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

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

备忘录

0%