动态规划

了解一下

零钱兑换

题目

image-20210613100037414

答案

1
2
3
4
5
6
7
8
9
10
11
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函数/数组的定义。自定向下

备忘录