动态规划
1. 背包问题
1.1. 二维dp数组
public class Knapsack {
static int knapsack(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weight[i - 1] <= j) {
// 01背包，可以选择放入或不放入
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
// 完全背包，可以放入多次或不放入
// dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
} else {
// 物品重量超过背包容量，不能放入
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] weight = { 2, 3, 4, 5 };
int[] value = { 3, 4, 5, 6 };
int capacity = 8;
System.out.println("Maximum value that can be obtained：" + knapsack(weight, value, capacity));
}
}
1.2. 一维dp数组
public static int knapsack(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[capacity];
}
2. 打家劫舍
2.1. 单向房屋
public class loot1 {
static int loot(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[2];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
int res = 0;
for (int i = 2; i < nums.length; i++) {
res = Math.max(dp[0] + nums[i], dp[1]);
dp[0] = dp[1];
dp[1] = res;
}
return dp[1];
}
public static void main(String[] args) {
int[] nums = { 2, 7, 9, 3, 1 };
System.out.println("偷窃到的最高金额：" + loot(nums));
}
}
2.2. 循环房屋
public class loot2 {
static int loot(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
return Math.max(lootAction(nums, 0, len - 1), lootAction(nums, 1, len));
}
static int lootAction(int[] nums, int start, int end) {
int x = 0, y = 0, z = 0;
for (int i = start; i < end; i++) {
y = z;
z = Math.max(x + nums[i], y);
x = y;
}
return z;
}
public static void main(String[] args) {
int[] nums = { 1, 2, 3, 1 };
System.out.println("偷窃到的最高金额：" + loot(nums));
}
}
3. 最长上升子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
import java.util.Arrays;
public class LengthOfLIS {
static int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 0;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
// 取dp[j] + 1的最大值
dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
}
return res;
}
public static void main(String[] args) {
int[] nums = { 0, 1, 0, 3, 2, 3 };
System.out.println("最长递增子序列的长度：" + lengthOfLIS(nums));
}
}
4. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
public class LengthOfLCS {
static int lengthOfLCS(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
String text1 = "abcde";
String text2 = "ace";
System.out.println("最长公共子序列的长度: " + lengthOfLCS(text1, text2));
}
}