动态规划的核心思想 -- 以空间换时间
复杂点说通过分解问题为子问题并存储子问题解来优化复杂计算的算法策略。
简单看个问题。
一，初始：求最长连续递增子序列
nums = [10,9,2,5,3,7,101,18]求上面数组中的最长连续递增子序列，输出其长度
暴力解法中我们需要以每个数为开头去遍历数组，得到最长的子数组。
会产生如下遍历
3,7,101
7,101
可以看到，有重复的计算。我们先用java写一下暴力解法。
暴力解法
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
int temp = 1; // 当前子序列的长度，初始为1（单个元素）
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] > nums[j - 1]) {
temp++;
} else {
break;
}
}
res = Math.max(res, temp); // 更新最长子序列的长度
}
return res;
}双重for循环，时间复杂度为 (O(n^2))，空间复杂度为 (O(1))。
动态规划
初始化dp的int数组。值为到当前位置的最大连续数。这样整个遍历完dp数组的值应该是
[1,1,1,2,1,2,3,1]。 可以看到最大长度为3。
/**
* 方法二： 动态规划求解连续递增子序列
* @param nums
* @return
*/
public int lengthOfLIS2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1; // 单个元素本身就是一个长度为 1 的连续递增子序列
int res = 1; // 初始化结果为 1
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1; // 当前元素本身可以作为一个新的连续递增子序列的起点
}
res = Math.max(res, dp[i]); // 更新最长子序列的长度
}
return res;
}时间复杂度：(O(n))
空间复杂度：(O(n))
二，升级：求最长递增子序列
nums = [10,9,2,5,3,7,101,18]求上面数组中的最长递增子序列，输出其长度
将上面一道题进行稍微变化一下，我们可以看出，现在的结果应该是2,3,7,101。输出结果应该是4。
如果不用动态规划，这道题有点难解。需要用到回溯+记忆，单纯的暴力解法并不适用。
比如我再加一个测试用例
nums =[0,1,0,3,2,3]
回溯法
/**
* 方法一： 暴力解法
* @param nums
* @return
*/
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int maxLen = 0;
for (int i = 0; i < nums.length; i++) {
maxLen = Math.max(maxLen, backtrack(nums, i, new ArrayList<>()));
}
return maxLen;
}
// 回溯法生成所有递增子序列
private int backtrack(int[] nums, int index, List<Integer> current) {
if (index >= nums.length) return current.size();
int maxLen = current.size(); // 不选当前元素的默认长度
// 选择当前元素的情况
if (current.isEmpty() || nums[index] > current.get(current.size() - 1)) {
current.add(nums[index]);
int lenWith = backtrack(nums, index + 1, current);
current.remove(current.size() - 1);
maxLen = Math.max(maxLen, lenWith);
}
// 不选当前元素的情况
int lenWithout = backtrack(nums, index + 1, current);
return Math.max(maxLen, lenWithout);
}时间复杂度： (O(2^n))
空间复杂度：O(n)
该方法容易超过时间限制
动态规划
这个就需要在上个动态规划样例中稍微改动一下。
我们先模拟一下对照样例生成的dp数组应该的样子。
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
int[] dp = {1, 1, 1, 2, 2, 3, 4, 4};
先举个简单的方便观察的例子
int[] nums = {1, 2, 3, 4, 2, 6, 7};
int[] dp = {1, 2, 3, 4, 1, 5, 6};
即便当数组为递减数组时，长度也会输出1
- 所以我们还是需要先将dp数组全部初始化1
- 第一次遍历，2 > 1的，所以dp[1] = dp[0] + 1;
- 第二次遍历，3 > 1的，所以dp[2] = dp[0] + 1; 然后 3 > 2的，所以 dp[2] = dp[1] + 1；
- ……
- 第五次遍历，6 > 4的，所以dp[5] = dp[3] + 1;但是6 > 2，不能得出dp[5] = dp[4] + 1,需要dp[4] + 1与当前的dp[5]的值进行比较。取最大的一个。
- ……
所以综上我们可以写出代码
/**
* 方法二： 动态规划求解递增子序列
* @param nums
* @return
*/
public int lengthOfLIS2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 1; // 初始化结果为 1
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
}
return res;
}时间复杂度为 O(n²)，空间复杂度为 O(n)。
三，再升级：删除最少元素，使剩余元素先递增后递减
动态规划
还是以刚刚的例子为例
nums = [10,9,2,5,3,7,101,18]删除最少元素，使剩余元素先递增后递减，输出最少需要删除多少元素。
通过上面两个例子，我们可以看出一个dp数组只能保存一个状态。
对于这道题，我们可以考虑使用两个dp数组来完成。
nums = [10,9,2,5,3,7,101,18]int[] dp1 = {1, 1, 1, 2, 2, 3, 4, 4}; //递增dp int[] dp2 = {4, 3, 1, 2, 1, 1, 2, 1}; //递减dp
可以看出在dp1[6] + dp2[6] = 6的时候是最大的，所以最大长度应该是dp1[6] + dp2[6] - 1 = 5；
因为6这个节点重复计算了，所以需要减1
那么就能得出答案需要删除：nums.length() - 5 = 3;
最少需要删除3个元素。
/**
* 方法二： 动态规划求解删除最少元素，使剩余元素先递增后递减
* @param nums
* @return
*/
public int lengthOfLIS3(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp1 = new int[n];
int[] dp2 = new int[n];
Arrays.fill(dp1, 1);
Arrays.fill(dp2, 1);
// 递增子序列
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp1[i] = Math.max(dp1[i], dp1[j] + 1);
}
}
}
// 递减子序列
for (int i = n - 2; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (nums[j] < nums[i]) {
dp2[i] = Math.max(dp2[i], dp2[j] + 1);
}
}
}
// 合并
int max = 0;
for (int i = 0; i < n; i++) {
if (dp1[i] + dp2[i] > max) {
max = dp1[i] + dp2[i];
}
}
return n - max - 1;
}四，看一道力扣原题
这道题可以换个角度看看，我们要求amount的最小硬币个数。可以构建dp[amount + 1]数组，
求从1 - amount间的所有最小个数。
换个简单的实例
输入：coins = [1, 2], amount = 5
以外层coins为循环，内层循环amount得到最小值
如上面例子。
初始化dp数组，因为要求最小，所以初始值应该为最大，且dp[0] = 0;
第一次外层循环1得到dp数组[0,1,2,3,4,5]
第二次外层循环2得到dp数组[0,1,1,2,2,3]
构建dp公式：
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
得到解法
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // 初始化为不可达标记
dp[0] = 0; // 基础情况
// 外层循环遍历硬币
for (int coin : coins) {
// 内层循环遍历金额（完全背包正序遍历）
for (int i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}