Jiaming Zhang's Blog
0%

算法-动态规划

发表于 更新于 分类于

动态规划相关算法题

现有司机N*2人，调度中心会将所有司机平分给A、B两区域，i号司机去A可得收入为income[i][0]，去B可得收入为income[i][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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public int driverMaxMoney(int[][] income) {
       if (income == null || income.length == 0 || (income.length & 1) != 0) {
           return 0;
       }
       int driverNumToA = income.length >> 1;
       // 缓存
       HashMap<Integer, HashMap<Integer, Integer>> cache = new HashMap<>();
       return process(income, 0, driverNumToA, cache);
   }

   /**
    * 
    * @param income 司机分配到A、B地区获取的钱数 income[i][0]表示i司机到A地区的收入，income[i][1]表示i司机到B地区的收入
    * @param index index位置及之后的司机分配的最大钱数
    * @param restForA A地区剩余的人数
    * @return
    */
   public int process(int[][] income, int index, int restForA, HashMap<Integer, HashMap<Integer, Integer>> cache) {
       // 先查询缓存是否已计算过 index-restForA 的组合
       if (cache.containsKey(index) && cache.get(index).containsKey(restForA)) {
           // 缓存命中
           return cache.get(index).get(restForA);
       }
       if (index == income.length) {
           return 0;
       }
       // A地区人满了，剩下的司机都只能去B地区
       if (restForA == 0) {
           return income[index][1] + process(income, index + 1, restForA, cache);
       }
       // B地区人满了，剩下的司机都只能去A地区
       if (income.length - index == restForA) {
           return income[index][0] + process(income, index + 1, restForA - 1, cache);
       }
       // A/B地区都没满，比较当前人去A或者去B两种方案的最大值
       int planA = income[index][0] + process(income, index + 1, restForA - 1, cache);
       int planB = income[index][1] + process(income, index + 1, restForA, cache);
       int ans = Math.max(planA, planB);
       // 添加到缓存中
       cache.put(index, new HashMap<>(restForA, ans));
       return ans;
   }

   /**
    * 动态规划填表做法
    * @param income
    * @return
    */
   public int driverMaxMoneyByDP(int[][] income) {
       int N = income.length;
       int M = N >> 1;
       // dp[i][j]表示第i个司机及以后，A地区有i个位置，分配的最大收入
       int[][] dp = new int[N+1][M+1];
       for (int i = N-1; i >= 0 ; i--) {
           for (int j = 0; j <= M; j++) {
               // A区人满了，只能去B区
               if (j == 0) {
                   dp[i][j] = income[i][1] + dp[i+1][j];
               }
               // B区人满了，只能去A区
               else if (N - i == j) {
                   dp[i][j] = income[i][0] + dp[i+1][j-1];
               }
               // A/B地区都没满
               else {
                   // 当前人去A情况下，获取的整体最大收入
                   int planA = income[i][0] + dp[i+1][j-1];
                   // 当前人去B情况下，获取的整体最大收入
                   int planB = income[i][1] + dp[i+1][j];
                   dp[i][j] = Math.max(planA, planB);
               }
           }
       }
       return dp[0][M];
   }

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

  • 插入一个字符

  • 删除一个字符

  • 替换一个字符

    https://leetcode-cn.com/problems/edit-distance

b466c347b42065b3a52b5257ce11b80 
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
class Solution {
    public int minDistance(String word1, String word2) {
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        int N = arr1.length;
        int M = arr2.length;
        // dp[i][j]表示word1[0:i]到word2[0:j]的最短编辑距离
        int[][] dp = new int[N+1][M+1];
        // 初始化dp矩阵边界
        for (int i = 0; i <= N; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= M; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[N][M];
    }
}

给定三个字符串s1、s2、s3，请你帮忙验证s3是否是由s1和s2交错组成的

https://leetcode-cn.com/problems/interleaving-string/

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
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        int N = c1.length;
        int M = c2.length;
        boolean[][] dp = new boolean[N+1][M+1];
        // 初始化dp边界
        dp[0][0] = true;
        for (int i = 1; i <= N; i++) {
            dp[i][0] = c1[i-1] == c3[i-1];
            if (!dp[i][0]) {
                break;
            }
        }
        for (int i = 1; i <= M; i++) {
            dp[0][i] = c2[i-1] == c3[i-1];
            if (!dp[0][i]) {
                break;
            }
        }
        // 根据dp方程求dp[i][j]
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                dp[i][j] = (c3[i + j - 1] == c1[i-1] && dp[i-1][j]) ||
                        (c3[i + j - 1] == c2[j-1] && dp[i][j-1]);
            }
        }
        return dp[N][M];
    }
}

数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，可以任意切分成若干个不相交的子数组。其中一定存在一种最优方案，使得切出异或和为0的子数组最多，返回这个最多数量

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
public static int mostXor2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[] dp = new int[N];
        int xor = 0;
        Map<Integer, Integer> xorMap = new HashMap<>();
        xorMap.put(0, -1);
        dp[0] = arr[0] == 0 ? 1 : 0;
        xorMap.put(arr[0], 0);
        for (int i = 1; i < N; i++) {
            // 如果arr[i]在最后一个异或和为0的子数组中
            // 计算xor[0:i]
            xor ^= arr[i];
            // 由于 a ^ 0 = a，假设最后一个异或和为0的分割子数组为last_xor_zero_arr
            // 则 xor ^ last_xor_zero_arr = xor，last_xor_zero_arr 的位置通过查询xor上一次出现的位置确定
            if (xorMap.containsKey(xor)) {
                int pre = xorMap.get(xor);
                dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
            }
            dp[i] = Math.max(dp[i], dp[i-1]);
            xorMap.put(xor, i);
        }
        return dp[N-1];
    }