#动态规划#
动态规划特点：
- 把原始问题划分成一系列子问题；
- 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间
- 自底向上地计算。（base case）
- 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）
300. 最长递增子序列
问题描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解题思路
问题拆分：首先，求出以数组中的每个元素结尾的最长递增子序列长度；然后取其中的最大值
base case：数组中仅有一个元素时，唯一的子序列是nums[0]，所以最长递增子序列长度为1
状态转移：以nums[i]结尾的最长递增子序列长度= 在nums[i]之前的以小于nums[i]的数结尾的最长递增子序列长度中的最大值 + 1
代码实现
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
//定义dp数组: dp[i]表示以nums[i]结尾的最长递增子序列长度
int[] dp = new int[len];
//以nums[0]结尾的最长子序列只有它自己
dp[0] = 1;
for(int i = 0; i < len; i++){
//以nums[i]结尾的最长递增子序列长度= nums[i]之前的以小于nums[i]的数结尾的最长递增子序列长度中的最大值 + 1
int max = 0;
for(int j = 0; j < i; j++){
if(nums[j] < nums[i] && max < dp[j]){
max = dp[j];
}
}
dp[i] = max + 1;
}
//返回dp数组中的最大值
int res = 0;
for(int n : dp){
if(res < n){
res = n;
}
}
return res;
}
}
- 时间复杂度:O(n^2)，n为数组中的元素
- 空间复杂度：O(n)，使用长度为 n的 dp数组保存子问题结果
152. 乘积最大子数组
问题描述
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
解题思路
由于此题数组中的元素既可能是正数（与正数相乘的数越大得到的乘积越大），也可能为负数（与负数的数越小得到的乘积才越大）
因此维护一个二维的dp数组存储以nums[i]结尾的最大/最小连续子数组乘积；
代码实现1-动态规划
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
//dp[i][0]表示以nums[i]结尾的最小连续子数组乘积
//dp[i][1]表示以nums[i]结尾的最大连续子数组乘积
int[][] dp = new int[len][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
int max = nums[0];
for(int i = 1; i < len; i++){
int minP = nums[i] * dp[i-1][0];
int maxP = nums[i] * dp[i-1][1];
dp[i][0] = Math.min(Math.min(minP,maxP),nums[i]);
dp[i][1] = Math.max(Math.max(minP,maxP),nums[i]);
//更新最值
max = Math.max(max, dp[i][1]);
}
return max;
}
}
- 时间复杂度：O(n)，n为数组中的元素
- 空间复杂度：O(n)，n为数组中的元素
上面的代码，在状态转移时，dp[i]只与dp[i-1]相关，因此，可以进行“状态压缩”，用变量来代替dp数组，降低空间复杂度。
代码实现-压缩空间
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
int dpMin = nums[0], dpMax = nums[0], max = nums[0];
for(int i = 1; i < len; i++){
int minP = nums[i] * dpMin;
int maxP = nums[i] * dpMax;
dpMin = Math.min(Math.min(minP,maxP),nums[i]);
dpMax = Math.max(Math.max(minP,maxP),nums[i]);
max = Math.max(max,dpMax);
}
return max;
}
}
参考资料：【算法复习】动态规划
