动态规划之数组压缩空间、星号技巧【3】

动态规划之数组压缩空间、星号技巧【3】

1 最小距离累加和

1.1 正常动规

//正常动态规划
public static int minPathSum1(int[][] m){
    //边界
    if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
        return 0;
    }
    int row = m.length;
    int col = m[0].length;
    int[][] dp = new int[row][col];
    //初始位置[0, 0] 不依赖于任何位置,只看自己的值
    dp[0][0] = m[0][0];
    //第一行
    for(int i = 1; i < col; i++){
        //对于每一列来说
        dp[0][i] = dp[0][i-1] + m[0][i];
    }
    //第一列
    for(int j = 1; j < row; j++){
        //对于每一行来说
        dp[j][0] = dp[j-1][0] + m[j][0];
    }
    //普遍范围
    for(int i = 1; i < row; i++){
        for(int j = 1; j < col; j++){
            //每一个位置都依赖于它的上左
            //可以选择左边也可以选择上边
            //选择最小的那个
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + m[i][j];
        }
    }
    return dp[row-1][col-1];
}
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

思考：如果题目所给的数组，有太多行怎么办呢？

可以将动态规划表，改为一维数组，如果行太多，则改成一行N列的一维数组

//压缩空间【时间复杂度不变】
public static int minPathSum2(int[][] m){
    if(m == null || m.length == 0 || m[0].length == 0 || m[0] == null){
        return 0;
    } 
    int row = m.length;
    int col = m[0].length;
    //假设行太多
    int[] dp = new int[col];
    dp[0] = m[0][0];
    //初始化数组[填充之前的第一行]
    for(int j = 1; j < col; j++){
        dp[j] = dp[j-1] + m[0][j];
    }
    //压缩空间
    for(int i = 1; i < row; i++){
        //记住最左边位置【之前的第一列】
        dp[0] += m[i][0];
        for(int j = 1; j < col; j++){
            //dp[j]：相当于之前的上方
            //dp[j-1]:相当于之前左方
            dp[j] = Math.min(dp[j-1], dp[j]) + m[i][j];
        }
    }
    return dp[col-1];
}
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

2 货币问题1【面值相同为两张、张数无限】

2.1 递归尝试

//arr:钱币数组
//aim:目标值
public static int coinWays(int[] arr, int aim) {
    return process(arr, 0, aim);
}

//arr:钱币数组
//index:当前所在位置
//rest:剩余的目标钱数
public static int process(int[] arr, int index, int rest) {
    if (rest < 0) {
        //剩余钱数小于零
        return 0;
    }
    if (index == arr.length) {
        return rest == 0 ? 1 : 0;
    } else {
        //选当前硬币与不选当前硬币【方法数和】
        return process(arr, index + 1, rest) + process(arr, index + 1, rest - arr[index]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 动态规划

//动态规划
public static int dp(int[] arr, int aim){
    int N = arr.length;
    //0-aim 共有aim+1个数
    //arr.length同理【会取到结尾就+1】
    int[][] dp = new int[N+1][aim+1];
    //base case【index为数组末尾， rest为0时候】
    dp[N][0] = 1;
    for(int index = N - 1; index >= 0; index--){
        for(int rest = aim; rest >= 0; rest--){
            dp[index][rest] = dp[index+1][rest] + (rest - arr[index] >= 0 ? dp[index+1][rest - arr[index]] : 0);
        }
    }
    return dp[0][aim];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3 货币问题2【面值相同为一张、张数无限】

3.1 尝试（zhang）

public static int coinsWay(int[] arr, int aim){
    if(arr == null || arr.length == 0 || aim < 0){
        return 0;
    }
    return process(arr, 0, aim);
}

//大体思路和货币问题1一样【只不过多了一层for循环，需要做暴力尝试】
public static int process(int[] arr, int index, int rest){
    if(index == arr.length){
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    //张数可以能为0，可能不为0【包含了选该货币和不选该货币的情况】
    for(int zhang = 0; zhang * arr[index] <= rest; zhang++){
        ways += process(arr, index+1, rest - zhang * arr[index]);
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.2 动态规划1（三层for）

//动态规划1：三层for循环
public static int dp1(int[] arr, int aim) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    //index+1 -> 上面的依赖下面的
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = aim; rest >= 0; rest--) {
            //穷举：张数
            int ways = 0;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                ways += dp[index + 1][rest - zhang * arr[index]];
            }
            dp[index][rest] = ways;
        }
    }
    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

3.2 动态规划2

//建立空间感：优化【√ = ※ + a】
//  ※   √
//      a
public static int dp2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = aim; rest >= 0; rest--) {
            //画格子：找规律    8      11      14  (建立空间感)
            //           3张3元    2张3元    1张3元
            //  ※   √
            //①获得我下面格子的值a
            dp[index][rest] = dp[index + 1][rest];
            //②如果没有越界，我直接获得我※号的位置
            if (rest - arr[index] >= 0) {
                dp[index][rest] += dp[index][rest - arr[index]];
            }
        }
    }
    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

4 货币问题3【每个值都是一张货币，张数有限】

>>前置类及方法

//收集纸币信息
public static class Info {
    //有哪些纸币
    public int[] coins;
    //每种纸币对应的张数
    public int[] zhangs;

    public Info(int[] coins, int[] zhangs) {
        this.coins = coins;
        this.zhangs = zhangs;
    }
}

//收集纸币信息[不同纸币对应数量]
public static Info getInfo(int[] arr) {
    Map<Integer, Integer> map = new Hashtable<>();
    for (int i = 0; i < arr.length; i++) {
        if (map.containsKey(arr[i])) {
            map.put(arr[i], map.get(arr[i]) + 1);
        } else {
            map.put(arr[i], 1);
        }
    }
    int N = map.size();
    int[] coins = new int[N];
    int[] zhangs = new int[N];
    int index = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        coins[index] = entry.getKey();
        zhangs[index++] = entry.getValue();
    }
    return new Info(coins, zhangs);
}
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

4.1 尝试（收集纸币信息）

//方法入口
public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] zhangs = info.zhangs;
    return process(coins, zhangs, 0, aim);
}

//递归调用方法
public static int process(int[] coins, int[] zhangs, int index, int rest) {
    int N = coins.length;
    if (index == N) {
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    for(int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++){
        ways += process(coins, zhangs, index+1, rest - zhang*coins[index]);
    }
    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

4.2 动态规划第一个版本（三个for）

//动态规划：第一个版本
public static int dp1(int[] arr, int aim){
    if(arr == null || arr.length == 0 || aim < 0){
        return 0;
    }
    Info info = getInfo(arr);
    //纸币数组
    int[] coins = info.coins;
    //每种纸币对应的张数
    int[] zhangs = info.zhangs;
    int N = coins.length;
    int[][] dp = new int[N+1][aim+1];
    dp[N][0] = 1;
    for(int i = N - 1; i >= 0; i--){
        for(int rest = aim; rest >= 0; rest--){
            int ways = 0;
            for(int zhang = 0; zhang * coins[i] <= rest && zhang <= zhangs[i]; zhang++){
                ways += dp[i+1][rest - zhang*coins[i]];
            }
            dp[i][rest] = ways;
        }
    }
    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

4.3 动态规划第二个版本（√、※）

//动态规划2：画表格，建立空间感，找规律
public static int dp2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] zhangs = info.zhangs;
    //纸币的种类
    int N = coins.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        //一行中的元素之间如果没有依赖，所以无论从左往右还是从右往左都可以【此处只能从左往右：因为我们在技巧上要依赖它的左边※】
        for (int rest = 0; rest <= aim; rest++) {
            //画表格，建立空间感，找规律
            //      ※    √
            // x          a(多算了一个x)
            dp[index][rest] = dp[index + 1][rest];
            if (rest - coins[index] >= 0) {
                dp[index][rest] += dp[index][rest - coins[index]];
            }
            //判断是否多算
            if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
                dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[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
24
25
26
27
28
29
30

5 圈问题【Bob Die】

5.1 递归尝试

//row * col 范围
//N * M 存活区域，超过该区域，bob掉沟里，死亡
//k bob一共走k步
public static double livePossibility1(int row, int col, int k, int N, int M) {
    return (double) process(row, col, k, N, M) / Math.pow(4, k);
}

//目前在row、col位置，还有rest步要走，走完了如果还在范围内，就获得一个生存点，返回总的生存点数
public static long process(int row, int col, int rest, int N, int M) {
    if (row < 0 || row == N || col < 0 || col == M) {
        return 0;
    }
    //还在棋盘中
    if (rest == 0) {
        return 1;
    }
    //还在棋盘中，且还有步数要走
    long up = process(row - 1, col, rest - 1, N, M);
    long down = process(row + 1, col, rest - 1, N, M);
    long left = process(row, col - 1, rest - 1, N, M);
    long right = process(row, col + 1, rest - 1, N, M);
    return up + down + left + right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.2 动态规划（三维）

//三维动态规划【三个变量】
public static double livePossibility2(int row, int col, int k, int N, int M){
	//根据N * M范围建立矩阵即可【取不到N、M】
    long[][][] dp = new long[N][M][k+1];
    // 根据尝试：rest == 0 -> 返回1
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            dp[i][j][0] = 1;
        }
    }
    for(int rest = 1; rest <= k; rest++){
        for(int r = 0; r < N; r++){
            for(int c = 0; c < M; c++){
                dp[r][c][rest] = pick(dp, N, M, r-1, c, rest-1);
                dp[r][c][rest] += pick(dp, N, M, r+1, c, rest-1);
                dp[r][c][rest] += pick(dp, N, M, r, c-1, rest-1);
                dp[r][c][rest] += pick(dp, N, M, r, c+1, rest-1);
            }
        }
    }
    return (double) dp[row][col][k] / Math.pow(4, k);
}

//控制范围【防止越界还计算】
public static long pick(long[][][] dp, int N, int M, int r, int c, int rest){
    if(r < 0 || r == N || c < 0 || c == M){
        return 0;
    }
    return dp[r][c][rest];
}
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