动态规划解题思路#

1
 // f(n) 计算第 n 个斐波那契数
2
    static int fib(int n) {
3
        if(n <= 1 && n >= 0) {
4
            return n;
5
        }
6
        return fib(n - 1) + fib(n - 2);
7
    }

1
    static long fib2(int n) {
2
        long[] memo = new long[n + 1];
3
        Arrays.fill(memo,-1);
4
        return dp(memo,n);
5

6
    }
7
    static long dp(long[] memo,int n) {
8
        if(n == 0 || n == 1) {
9
            return n;
10
        }
11
        if(memo[n] != -1) {
12
            return memo[n];
13
        }
14
        memo[n] = dp(memo,n - 1) + dp(memo,n - 2);
15
        return memo[n];
16
    }

1
class Solution {
2
    public int coinChange(int[] coins, int amount) {
3
        int[] dp = new int[amount + 1];
4
        Arrays.fill(dp,amount + 1);
5
        dp[0] = 0;
6
        for(int i = 0;i<dp.length;i++) {
7
            for(int coin : coins) {
8
                if(i - coin < 0) {
9
                    continue;
10
                }
11
                dp[i] = Math.min(dp[i],1 + dp[i - coin]);
12
            }
13
        }
14
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
15
    }
16
}

1
class Solution {
2
    int[] memo;
3

4
    public int coinChange(int[] coins, int amount) {
5
        memo = new int[amount + 1];
6
        // 备忘录初始化为一个不会被取到的特殊值，代表还未被计算
7
        Arrays.fill(memo, -666);
8

9
        return dp(coins, amount);
10
    }
11

12
    int dp(int[] coins, int amount) {
13
        if (amount == 0) return 0;
14
        if (amount < 0) return -1;
15
        // 查备忘录，防止重复计算
16
        if (memo[amount] != -666)
17
            return memo[amount];
18

19
        int res = Integer.MAX_VALUE;
20
        for (int coin : coins) {
21
            // 计算子问题的结果
22
            int subProblem = dp(coins, amount - coin);
23
            // 子问题无解则跳过
24
            if (subProblem == -1) continue;
25
            // 在子问题中选择最优解，然后加一
26
            res = Math.min(res, subProblem + 1);
27
        }
28
        // 把计算结果存入备忘录
29
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
30
        return memo[amount];
31
    }
32
}