动态规划进阶 — — 斜率优化【3】

动态规划进阶 — — 斜率优化【3】

1 打怪兽问题

1.1 尝试

//杀怪兽
public class KillMonsterDemo {

    /**
     * @param N 怪兽初始血量
     * @param M 每次打击伤害范围[0, M]
     * @param K 剩余打击次数
     * @return
     */
    public static double right(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        long kill = process(K, M, N);
        return (double) ((double) kill / (double) all);
    }

    //怪兽还剩hp点血
    //每次的伤害在[0~M]范围上
    //还有times次数可以砍
    //返回砍死的情况数
    public static long process(int times, int M, int hp){
        if(times == 0){
            //<0 ： 鞭尸
            return hp <= 0 ? 1 : 0;
        }
        if(hp <= 0){
            return (long)(Math.pow(M+1, times));
        }
        long ways = 0;
        for(int i = 0; i <= M; i++){
            ways += process(times - 1, M, hp - i);
        }
        return ways;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1.2 动态规划

//递归直接转动态规划
/**
 * @param N 怪兽初始血量
 * @param M 每次打击伤害范围[0, M]
 * @param K 剩余打击次数
 * @return
 */
public static double dp1(int N, int M, int K) {
    if (N < 1 || M < 1 || K < 1) {
        return 0;
    }
    long all = (long) Math.pow(M + 1, K);
    long[][] dp = new long[K + 1][N + 1];
    dp[0][0] = 1;
    for (int times = 1; times <= K; times++) {
        //怪兽血量为0时
        dp[times][0] = (long) Math.pow(M + 1, times);
        for (int hp = 1; hp <= N; hp++) {
            long ways = 0;
            for (int i = 0; i <= M; i++) {
                if (hp - i >= 0) {
                    ways += dp[times - 1][hp - i];
                } else {
                    //怪兽血量小于0，鞭尸
                    //此次砍了之后剩下次数times-1次
                    ways += (long) Math.pow(M + 1, times - 1);
                }
            }
            dp[times][hp] = ways;
        }
    }
    long kill = dp[K][N];
    return (double) ((double) kill / (double) all);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

1.3 动态规划2（斜率优化）

//优化版：动态规划

/**
 * @param N 怪兽初始血量
 * @param M 每次打击伤害范围[0, M]
 * @param K 剩余打击次数
 * @return
 */
public static double dp2(int N, int M, int K) {
    if (N < 1 || M < 1 || K < 1) {
        return 0;
    }
    long all = (long) Math.pow(M + 1, K);
    long[][] dp = new long[K + 1][N + 1];
    dp[0][0] = 1;
    for (int times = 1; times <= K; times++) {
        dp[times][0] = (long) Math.pow(M + 1, times);
        for (int hp = 1; hp <= N; hp++) {
            //多算了
            dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
            if (hp - 1 - M >= 0) {
            	//多加的
                dp[times][hp] -= dp[times - 1][hp - 1 - M];
            } else {
            	//虽然矩阵中没有该范围，但是还是应该根据公式减去
                dp[times][hp] -= Math.pow(M + 1, times - 1);
            }
        }
    }
    long kill = dp[K][N];
    return (double) ((double) kill / (double) all);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2 货币问题

2.1 尝试

public static int minCoins(int[] arr, int aim) {
    return process(arr, 0, aim);
}

// arr[index...]面值，每种面值张数自由选择，
// 搞出rest正好这么多钱，返回最小张数
// 拿Integer.MAX_VALUE标记怎么都搞定不了
public static int process(int[] arr, int index, int rest) {
    if (index == arr.length) {
        //rest为0，此时不用钱了
        return rest == 0 ? 0 : Integer.MAX_VALUE;
    } else {
        int ans = Integer.MAX_VALUE;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
        	//选择zhang这么多纸币时，完成rest - zhang * arr[index]需要next张
            int next = process(arr, index + 1, rest - zhang * arr[index]);
            if (next != Integer.MAX_VALUE) {
                ans = Math.min(ans, zhang + next);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.2 动态规划

public static int dp1(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }
    int N = arr.length;
    //行：index位置
    //列：rest
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 0;
    //当前已经走到了arr末尾，rest的值不为0->失败：用Integer.MAX_VALUE表示
    for (int j = 1; j <= aim; j++) {
        dp[N][j] = Integer.MAX_VALUE;
    }
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ans = Integer.MAX_VALUE;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                int next = dp[index + 1][rest - zhang * arr[index]];
                if (next != Integer.MAX_VALUE) {
                    ans = Math.min(ans, zhang + next);
                }
            }
            dp[index][rest] = ans;
        }
    }
    return dp[0][aim];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.3 动态规划2（斜率优化）

//斜率优化
public static int dp2(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 0;
    for (int j = 1; j <= aim; j++) {
        dp[N][j] = Integer.MAX_VALUE;
    }
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            //判断之前有没有更小的值
            if (rest - arr[index] >= 0
                    && dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
                dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] + 1);
            }
        }
    }
    return dp[0][aim];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3 分裂数问题

给定一个正数n，求n的裂开方法数，
规定：后面的数不能比前面的数小
比如4的裂开方法有：
1+1+1+1、1+1+2、1+3、2+2、4
5种，所以返回5

3.1 尝试

//n为正数
public static int ways(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    //表明前一个数是1，此时的数为n，等着分裂
    return process(1, n);
}

//上一个拆出来的数是pre
//还剩rest需要拆
//返回拆解的方法数
public static int process(int pre, int rest) {
    if (rest == 0) {
        return 1;
    }
    if (pre > rest) {
        return 0;
    }
    int ways = 0;
    for (int first = pre; first <= rest; first++) {
        ways += process(first, rest - first);
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.2 动态规划

public static int dp1(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int[][] dp = new int[n + 1][n + 1];
    for (int pre = 1; pre <= n; pre++) {
        // pre rest = 0
        // pre rest = pre
        dp[pre][0] = 1;
        dp[pre][pre] = 1;
    }
    for (int pre = n - 1; pre >= 1; pre--) {
        for (int rest = pre + 1; rest <= n; rest++) {
            int ways = 0;
            for (int first = pre; first <= rest; first++) {
                ways += dp[first][rest - first];
            }
            dp[pre][rest] = ways;
        }
    }
    return dp[1][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3.3 动态规划2（斜率优化，画表格，找依赖）

//画图：一目了然
public static int dp2(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int[][] dp = new int[n + 1][n + 1];
    for (int pre = 1; pre <= n; pre++) {
        dp[pre][0] = 1;
        dp[pre][pre] = 1;
    }
    for (int pre = n - 1; pre >= 1; pre--) {
        for (int rest = pre + 1; rest <= n; rest++) {
            dp[pre][rest] = dp[pre + 1][rest];
            dp[pre][rest] += dp[pre][rest - pre];
        }
    }
    return dp[1][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21