1.两个字符串的删除操作
与求解最长公共子序列方法一致，求出来后使用两个字符串的长度减去最长公共子序列长度即可。
package com.dreams.dynamicprogramming;
/**
* 两个字符串的删除操作
*/
public class Leetcode538 {
public static void main(String[] args) {
Leetcode538 code = new Leetcode538();
System.out.println(code.minDistance("eat", "sea"));
}
public int minDistance(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] chars1 = text1.toCharArray();
char[] chars2 = text2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
char x = chars1[i - 1];
for (int j = 1; j < n + 1; j++) {
char y = chars2[j - 1];
if (x == y) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - 2 * dp[m][n];
}
}
2.最长递增子序列
流程：
1 2 3 4
1 3 6 4 9
1 13 16 14 19
136 134 139
169
1369
149
1349
(1) (2) (3) (3) (4)
4代码：
package com.dreams.dynamicprogramming;
import java.util.Arrays;
/**
* 最长递增子序列
*/
public class Leetcode300 {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { // 满足了升序条件
// 用之前递增子序列的最大长度 + 1 更新当前长度
dp[i] = Integer.max(dp[i], dp[j] + 1);
}
}
System.out.println(Arrays.toString(dp));
}
return Arrays.stream(dp).max().getAsInt();
}
public static void main(String[] args) {
Leetcode300 code = new Leetcode300();
System.out.println(code.lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
}
}还有一种更优解是二分查找找到应该插入。遍历数组 nums，对于每个元素 num，在 dp 数组中使用二分查找找到应该插入的位置 index。如果 index 小于 0，则说明当前元素 num 比 dp[0, len) 中的所有元素都小，因此将其插入到 dp[-index-1] 的位置上，这里会覆盖之前的值，因为是找最长递增子序列所以直接覆盖就行。如果 index 大于等于 0，则说明当前元素 num 在 dp 数组中找到了一个相等的元素，直接忽略。如果 index 等于 len，则说明当前元素 num 比 dp[0, len) 中的所有元素都大，也就是说它就是递增子序列，因此更新 len 为 len + 1。最后返回 len，即为最长递增子序列的长度。
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0; // 记录当前最长递增子序列的长度
for (int num : nums) {
int index = Arrays.binarySearch(dp, 0, len, num);
if (index < 0) {
//应该插入的位置
index = -(index + 1);
}
dp[index] = num;
if (index == len) {
len++;
}
}
return len;
}
3.打家劫舍
演示：
价值 0 1 2 3 4
0 0 0 0 0
0(7) 7 0 0 0 0
1(2) 7 7 0 0 0
2(9) 2 7 11 0 0
3(3) 2 7 11 11 0
4(1) 2 7 11 11 12公式：
dp[i] = max(dp[i-2]+value, dp[i-1])
代码：
package com.dreams.dynamicprogramming;
/**
* 打家劫舍 - 动态规划
*/
public class HouseRobberLeetcode198 {
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Integer.max(nums[1], nums[0]);
for (int i = 2; i < len; i++) {
dp[i] = Integer.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[len - 1];
}
public static void main(String[] args) {
HouseRobberLeetcode198 code = new HouseRobberLeetcode198();
System.out.println(code.rob(new int[]{2, 7, 9, 3, 1}));
}
}
4.旅行商问题
旅行商问题（TSP）是一个经典的组合优化问题，涉及到在给定一组城市和它们之间的距离（或成本）的情况下，找到一条最短路径，使得每个城市都恰好被访问一次，并且最后回到起始城市。
注意：最小生成树（MST）是另一个经典的问题，涉及到在一个连通的无向图中找到一棵包含所有顶点的树，并且边的权重之和最小。虽然TSP和MST都涉及到图论和路径优化，但它们解决的是不同的问题。MST解决的是连通性和最小权重的问题，而TSP解决的是路径的问题。尽管可以将TSP问题转化为MST问题，但是直接使用MST来解决TSP并不是一个可行的方法，因为MST并不一定会包含TSP所需的路径。
使用二进制表示城市可达
0 1 2 3 4 5 6 7 j 剩余城市集合
0 1 2 1|2 3 1|3 2|3 1|2|3
0
1
2
3
i 出发城市
000 没城市 0
001 1号 1
010 2号 2
100 3号 4
011 1和2 3
101 1和3 5
110 2和3 6
111 1和2和3 7逻辑：
出发城市 i
剩余城市集合 j
遍历 j 时的变量 k （剩余的某一个城市)
d(i, j) => min(
g[i][k] + d(k, j去掉k)
g[i][k] + d(k, j去掉k)
g[i][k] + d(k, j去掉k)
)
d(k,空) => 从k回到起点 => g[k][i]代码：
package com.dreams.dynamicprogramming;
import java.util.Arrays;
import java.util.stream.Collectors;
/**
* 旅行商问题
*/
public class TravellingSalesmanProblem {
public static void main(String[] args) {
int[][] graph = {
{0, 1, 2, 3},
{1, 0, 6, 4},
{2, 6, 0, 5},
{3, 4, 5, 0},
};
System.out.println(tsp(graph));
}
static int tsp(int[][] g) {
int m = g.length; // 城市数目
int n = 1 << (m - 1); // 剩余城市的组合数 2^(m-1)
int[][] dp = new int[m][n];
// 填充第0列
for (int k = 0; k < m; k++) {
dp[k][0] = g[k][0];
}
print(dp);
// 填充后续列
for (int j = 1; j < n; j++) {
for (int i = 0; i < m; i++) {
dp[i][j] = Integer.MAX_VALUE / 2;
if(contains(j, i)) continue; // 剩余城市集合已包含出发城市，不合理
// 填充单元格
for (int k = 0; k < m; k++) {
if(contains(j, k)) { // 只对剩余城市集合中的城市进行处理
dp[i][j] = Integer.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);
}
}
}
}
print(dp);
return dp[0][n - 1];
}
static boolean contains(int set, int city) {
return (set >> (city - 1) & 1) == 1;
}
static int exclude(int set, int city) {
return set ^ (1 << (city - 1));
}
static void print(int[][] dist) {
System.out.println("-------------------------");
for (int[] row : dist) {
System.out.println(Arrays.stream(row).boxed()
.map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x))
.map(s -> String.format("%2s", s))
.collect(Collectors.joining(",", "[", "]")));
}
}
}
参考
