算法题解之动态规划

分类: IT文章 • 2023-11-08 21:26:39

Arithmetic Slices

算术片的个数

思路（最优解）：序列型dp。每次记录一下以当前数为末尾的算术片的最大长度以及数的等差值。下一次就能求出算术片增加的个数。使用滚动指针来优化。时间复杂度O(n)，空间复杂度O(1)。

 1 public class Solution {
 2     public int numberOfArithmeticSlices(int[] A) {
 3         if (A.length < 3) {
 4             return 0;
 5         }
 6         
 7        int prev_res = 0;
 8        int prev_length = 2;
 9        int prev_diff = A[1] - A[0];
10        
11        for (int i = 2; i < A.length; i++) {
12            if (prev_diff == A[i] - A[i - 1]) {
13                prev_res += prev_length - 1;
14                prev_length++;
15            } else {
16                prev_length = 2;
17                prev_diff = A[i] - A[i - 1];
18            }
19        }
20        return prev_res;
21     }
22 }

View Code

Climbing Stairs

爬楼梯

思路：滚动指针优化到O(1)空间。开一个大小为2的数组，用模2方式来求解。

 1 public class Solution {
 2     public int climbStairs(int n) {
 3         if (n == 1) {
 4             return 1;
 5         }
 6         int[] dp = new int[2];
 7         dp[0] = 1;
 8         dp[1] = 2;
 9         
10         for (int i = 2; i < n; i++) {
11             dp[i % 2] = dp[(i - 1) % 2] + dp[(i - 2) % 2];
12         }
13         return dp[(n - 1) % 2];
14     }
15 }

View Code

Drop Eggs II

扔鸡蛋II

思路：状态：设一种丢法在最坏情况下需要丢p次能确定结果，状态dp[i][j]表示i个鸡蛋和j层楼的所有丢法的最小p值。

　　　方程：对于i个蛋，j层楼，要确定它的所有丢法的最小p值。先假定第一次在第k层丢（1<=k<=j），如果蛋碎了，那么我们只需要用剩下的鸡蛋测试k层以下的楼层，所以问题简化为k-1层和i-1个鸡蛋,因此对应的次数是dp[i-1][k-1]+1；如果蛋不碎，那么我们只需要检查比k较高的楼层; 所以问题简化为 j-k 和i个鸡蛋，即dp[i][j-k]+1。最坏情况应该是两者的最大值。而所有k(1~j)对应的次数的最小值就是最小p值。

　　　初始化：对于一个蛋的问题，p值是楼层数j。即dp[1][j] = j.

　　　结果：dp[m][n]

public class Solution {
    /**
     * @param m the number of eggs
     * @param n the umber of floors
     * @return the number of drops in the worst case
     */
    public int dropEggs2(int m, int n) {
        // Write your code here
        int[][] dp = new int[m+1][n+1];
        
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        
        for (int i = 2; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE; 
                for (int first = 1; first <= j; first++) {
                    dp[i][j] = Math.min(Math.max(dp[i-1][first - 1] + 1, dp[i][j - first] + 1),
                    dp[i][j]);
                }
            }
        }
        
        return dp[m][n];
    }
}

View Code

Is Subsequence

判断是否是子序列

思路1:典型的双序列动态规划。状态dp[i][j]表示s的前i个字符是否是t的前j个字符的子序列。时间复杂度O(s*t),空间复杂度O(s*t)，使用滚动数组可以讲空间优化到O(t)。

 1 public class Solution {
 2     public boolean isSubsequence(String s, String t) {
 3         boolean[][] dp = new boolean[s.length() + 1][t.length() + 1];
 4         
 5         for (int j = 0; j <= t.length(); j++) {
 6             dp[0][j] = true;
 7         }
 8         
 9         for (int i = 1; i <= s.length(); i++) {
10             for (int j = 1; j <= t.length(); j++) {
11                 if (dp[i][j - 1]) {
12                     dp[i][j] = true;
13                 } else {
14                     dp[i][j] = dp[i - 1][j - 1] && s.charAt(i - 1) == t.charAt(j - 1);
15                 }
16             }
17         }
18         return dp[s.length()][t.length()];
19     }
20 }

View Code

思路2:使用two pointers。时间复杂度O(t)，空间复杂度O(1)。

 1 public class Solution {
 2     public boolean isSubsequence(String s, String t) {
 3         if (s.length() == 0) return true;
 4         int indexS = 0, indexT = 0;
 5         while (indexT < t.length()) {
 6             if (t.charAt(indexT) == s.charAt(indexS)) {
 7                 indexS++;
 8                 if (indexS == s.length()) return true;
 9             }
10             indexT++;
11         }
12         return false;
13     }
14 }

View Code

思路3（最优解）：改进的two pointers，使用indexOf函数，时间复杂度仍然是O(t)。但是思路2调用了t次charAt函数，而这个方法只调用了s次函数。虽然时间复杂度相同，但是实际运行起来更快。

 1 public class Solution {
 2     public boolean isSubsequence(String s, String t) {
 3         if (s.length() == 0) return true;
 4         int pt = 0;
 5         for (int ps = 0; ps < s.length(); ps++) {
 6             char c = s.charAt(ps);
 7             pt = t.indexOf(c, pt);
 8             if (pt == -1) {
 9                 return false;
10             }
11             pt++;
12         }
13         return true;
14     }
15 }

View Code

k Sum

k数和

思路：一道三维动态规划，状态和方程都比较容易想，初始化要想一下。

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int kSum(int A[], int k, int target) {
        // write your code here
        int[][][] dp = new int[A.length + 1][k + 1][target + 1];
        for (int i = 1; i < A.length; i++) {
            for (int m = 1; m < target; m++) {
                if (A[i - 1] == m) {
                    dp[i][1][m] = 1;
                } else {
                    dp[i][1][m] = dp[i - 1][1][m];
                }
            }
        }
        
        for (int i = 2; i <= A.length; i++) {
            for (int j = 2; j <= Math.min(i, k); j++) {
                for (int m = 1; m <= target; m++) {
                    if (A[i - 1] < m) {
                        dp[i][j][m] = dp[i - 1][j - 1][m - A[i - 1]];
                    }
                    dp[i][j][m] += dp[i - 1][j][m];
                }
            }
        }
        return dp[A.length][k][target];
    }
}

View Code

Longest Increasing Subsequence

最长递增子序列

思路1：LIS是一道经典的dp题。用O(n^2)来做是一道简单的序列型动态规划。

 1 public class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 0;
 5         }
 6         
 7         int[] dp = new int[nums.length];
 8         dp[0] = 1;
 9         for (int i = 1; i < dp.length; i++) {
10             dp[i] = 1;
11             for (int j = 0; j <= i - 1; j++) {
12                 if (nums[j] < nums[i]) {
13                     dp[i] = Math.max(dp[i], 1 + dp[j]);
14                 }
15             }
16         }
17         int res = 0;
18         for (int i = 0; i < dp.length; i++) {
19             res = Math.max(res, dp[i]);
20         }
21         return res;
22     }
23 }

View Code

思路2（最优解）：这道题还存在O(nlgn)的解法。在思路1中，每次我们计算dp[i]的时候，都要往前面遍历找到一个nums[j]，使得nums[j] < nums[i]并且dp[j]值最大。在这个过程中其实有些数我们不用找。比如说长度为2的子序列有（3，5），（3，10），（2，4），那么我们只需要与4比较就可以，而不需要与5和10比较。因此我们定义一个数组B，其中B[i]表示长度为i的所有子序列中最小的末尾数。可以证明B是一个单调递增的数组。因此每次我们只需要使用二分查找找到小于nums[i]的最大值，返回它的长度i即可。

 1 public class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 0;
 5         }
 6         
 7         int res = 0;
 8         int[] B = new int[nums.length + 1];
 9         for (int i = 0; i < B.length; i++) {
10             B[i] = Integer.MAX_VALUE;
11         }
12         
13         for (int i = 0; i < nums.length; i++) {
14             int len = binarySearch(B, nums[i]) + 1;
15             res = Math.max(res, len);
16             B[len] = Math.min(B[len], nums[i]);
17         }
18         
19         return res;
20     }
21     
22     public int binarySearch(int[] B, int k) {
23         int start = 0;
24         int end = B.length - 1;
25         while (start + 1 < end) {
26             int mid = (start + end) / 2;
27             if (B[mid] >= k) {
28                 end = mid;
29             } else {
30                 start = mid;
31             }
32         }
33         if (B[end] < k) {
34             return end;
35         }
36         if (B[start] < k) {
37             return start;
38         }
39         return 0;
40     }
41 }

View Code

Minimum Adjustment Cost

最小调整代价

思路：状态：dp[i][j]表示对0～i的数做调整，最后一个数调整到数j的最小代价。

　　　方程：dp[i][j] = min(dp[i-1][m]) + cost(i,j)，即序列0~i-1做调整，最后一个数调整到m的代价的最小值，加上第i个数调整到j的代价。为保证满足条件，m的范围是（j - taget ~ j + target）。

　　　初始化：对于dp[0][j]，就是与j的差值。

　　结果：dp矩阵最后一行的最小值。

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        // write your code here
        
        int[][] dp = new int[A.size()][101];
        for (int j = 1; j < 101; j++) {
            dp[0][j] = Math.abs(j - A.get(0));
        }
        
        for (int i = 1; i < A.size(); i++) {
            for (int j = 1; j < 101; j++) {
                int cost = Math.abs(j - A.get(i));
                
                int min = Math.max(1, j - target);
                int max = Math.min(100, j + target);
                
                int pre_min_cost = Integer.MAX_VALUE;
                for (int m = min; m <= max; m++) {
                    pre_min_cost = Math.min(dp[i-1][m], pre_min_cost);
                }
                dp[i][j] = pre_min_cost + cost;
            }
        }
        
        int res = Integer.MAX_VALUE;
        for (int j = 1; j < 101; j++) {
            res = Math.min(dp[A.size() - 1][j], res);
        }
        return res;
    }
}

View Code

Partition Equal Subset Sum

和相同的二划分

思路1:每个划分的和应该是总和的一半，问题转化为01背包问题。状态dp[i][j]表示前j个数能否恰好装满容量为j的背包。

 1 public class Solution {
 2     public boolean canPartition(int[] nums) {
 3         int sum = 0;
 4         for (int num : nums) {
 5             sum += num;
 6         }
 7         if (sum % 2 != 0) {
 8             return false;
 9         }
10         
11         ／／转化为01背包问题
12         int capacity = sum / 2;
13         boolean[][] dp = new boolean[capacity + 1][nums.length + 1];
14         
15         dp[0][0] = true;
16         for (int i = 0; i <= capacity; i++) {
17             for (int j = 1; j <= nums.length; j++) {
18                 if (nums[j - 1] <= i) {
19                     dp[i][j] = dp[i - nums[j - 1]][j - 1] || dp[i][j - 1];
20                 } else {
21                     dp[i][j] = dp[i][j - 1];
22                 }
23             }
24         }
25         
26         return dp[capacity][nums.length];
27         
28     }
29 }

View Code

思路2(最优解):将思路1用滚动数组优化，这里在循环时要将背包容量i改为从大到小循环（见01背包问题的空间优化）。

 1 public class Solution {
 2     public boolean canPartition(int[] nums) {
 3         int sum = 0;
 4         for (int num : nums) {
 5             sum += num;
 6         }
 7         if (sum % 2 != 0) {
 8             return false;
 9         }
10         
11         int capacity = sum / 2;
12         boolean[] dp = new boolean[capacity + 1];
13         
14         dp[0] = true;
15         for (int j = 1; j <= nums.length; j++) {
16             for (int i = capacity; i >= 0; i--) {
17                 if (nums[j - 1] <= i) {
18                     dp[i] = dp[i - nums[j - 1]] || dp[i];
19                 } 
20             }
21         }
22         
23         return dp[capacity];
24         
25     }
26 }

View Code

Regular Expression Matching

正则表达式匹配

思路：是一道双序列型动态规划，注意方程与通配符匹配的不同之处。

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         int m = s.length(), n = p.length();
 4         char[] ws = s.toCharArray();
 5         char[] wp = p.toCharArray();
 6         boolean[][] dp = new boolean[m+1][n+1];
 7         
 8         dp[0][0] = true;
 9         if (m > 0 && n > 0) {
10             dp[1][1] = wp[0] == '.' || wp[0] == ws[0];
11         }
12         
13         for (int j = 1; j <= n; j++) {
14             if (wp[j - 1] == '*') {
15                 dp[0][j] = j == 1 ? true : dp[0][j - 2] || dp[0][j - 1];
16             } 
17         }
18         for (int i = 1; i <= m; i++) {
19             dp[i][0] = false;
20         }
21         
22         for (int i = 1; i <= m; i++) {
23             for (int j = 2; j <= n; j++) {
24                 if (wp[j-1] == '.' || ws[i-1] == wp[j-1]) {
25                     dp[i][j] = dp[i-1][j-1];
26                 } else if (wp[j-1] == '*') {
27                     if (wp[j-2] == '*') {
28                         dp[i][j] = dp[i][j-1];
29                     } else {
30                         dp[i][j] = dp[i][j-2];
31                         if (wp[j-2] == ws[i-1] || wp[j-2] == '.') {
32                             dp[i][j] |= dp[i-1][j];
33                         }
34                     }
35                 }
36             }
37         }
38         return dp[m][n];
39     }
40 }

View Code

Word Break II

切分单词II

思路：用wordbreak I 动态规划的结果，来为搜索做剪枝，避免不必要的搜索，保留isWord[i][j]数组可以避免每次重复的切割字符串。如果用动态规划中保留中间结果的方法会超时，因为保留了很多不必要的中间结果，而保留中间结果既耗时又耗空间。

public class Solution {
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        // Write your code here
        boolean[] dp = new boolean[s.length() + 1];
        
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(word.length(), maxLen);
        }
        
        boolean[][] isWord = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String word = s.substring(i, j + 1);
                isWord[i][j] = wordDict.contains(word);
            }
        }
        
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j]) {
                    if (isWord[j][i - 1]) {
                        dp[i] = true;
                        break;
                    }
                }   
            }
        }
        List<String> res = new ArrayList<String>();
        search(res, isWord, dp, s.length() - 1, new ArrayList<String>(), s);
        return res;
    }
    
    public void search(List<String> res, boolean[][] isWord, 
            boolean[] dp, int end, List<String> cur, String s) {
        if (end < 0) {
            StringBuilder sb = new StringBuilder();
            for (int i = cur.size() - 1; i >= 0; i--) {
                sb.append(cur.get(i));
                if (i != 0) {
                    sb.append(" ");
                }
            }
            res.add(sb.toString());
        }
        
        for (int i = end; i >= 0; i--) {
            if (isWord[i][end] && dp[i]) {
                cur.add(s.substring(i, end + 1));
                search(res, isWord, dp, i - 1, cur, s);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

View Code

Wildcard Matching

通配符匹配

思路：属于双序列型动态规划，（注意题目中假设了只有p中含有通配符）。

　　　状态：dp[i][j]表示s的前i个字符组成的前缀串与p的前j个字符组成的前缀串是否匹配。

　　　方程：判断两个字符串是否匹配，有两种情况：

　　　　　　1 p的最后一个字母不为'*'，则要求最后一个字母匹配（相等或其中一个字母为'?'），且前i-1字串与前j-1字串匹配；

　　　　　　2 p的最后一个字母为'*'，如果它匹配s的最后一个空字符串，则等价于看dp[i][j-1]，如果它匹配s末尾某个非空字符串，则等价于看dp[i-1][j]。

　　　初始化：初始化第0行第0列；

　　　结果：dp[slen][plen]。

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         int m = s.length(), n = p.length();
 4         char[] ws = s.toCharArray();
 5         char[] wp = p.toCharArray();
 6         boolean[][] dp = new boolean[m+1][n+1];
 7         dp[0][0] = true;
 8         for (int j = 1; j <= n; j++) {
 9             dp[0][j] = dp[0][j-1] && wp[j-1] == '*';
10         }
11         for (int i = 1; i <= m; i++) {
12             dp[i][0] = false;
13         }
14         for (int i = 1; i <= m; i++) {
15             for (int j = 1; j <= n; j++) {
16                 if (wp[j-1] == '?' || ws[i-1] == wp[j-1]) {
17                     dp[i][j] = dp[i-1][j-1];
18                 }
19                 else if (wp[j-1] == '*') {
20                     dp[i][j] = dp[i-1][j] || dp[i][j-1];
21                 }
22             }
23         }
24         return dp[m][n];
25     }
26 }

View Code

算法题解之动态规划

Arithmetic Slices

Climbing Stairs

Drop Eggs II

Is Subsequence

k Sum

Longest Increasing Subsequence

Minimum Adjustment Cost

Partition Equal Subset Sum

Regular Expression Matching

Word Break II

Wildcard Matching

相关推荐