#動(dòng)態(tài)規(guī)劃#
動(dòng)態(tài)規(guī)劃特點(diǎn)：
- 把原始問題劃分成一系列子問題值朋；
- 求解每個(gè)子問題僅一次位谋，并將其結(jié)果保存在一個(gè)表中负饲，以后用到時(shí)直接存取矮烹，不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間
- 自底向上地計(jì)算腋逆。（base case）
- 整體問題最優(yōu)解取決于子問題的最優(yōu)解（狀態(tài)轉(zhuǎn)移方程）（將子問題稱為狀態(tài)岳锁，最終狀態(tài)的求解歸結(jié)為其他狀態(tài)的求解）
300. 最長(zhǎng)遞增子序列
問題描述
給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度蒋畜。
子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序撞叽。例如姻成，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列插龄。
解題思路
問題拆分：首先，求出以數(shù)組中的每個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度科展；然后取其中的最大值
base case：數(shù)組中僅有一個(gè)元素時(shí)均牢，唯一的子序列是nums[0]，所以最長(zhǎng)遞增子序列長(zhǎng)度為1
狀態(tài)轉(zhuǎn)移：以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度= 在nums[i]之前的以小于nums[i]的數(shù)結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度中的最大值 + 1
代碼實(shí)現(xiàn)
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
//定義dp數(shù)組: dp[i]表示以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度
int[] dp = new int[len];
//以nums[0]結(jié)尾的最長(zhǎng)子序列只有它自己
dp[0] = 1;
for(int i = 0; i < len; i++){
//以nums[i]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度= nums[i]之前的以小于nums[i]的數(shù)結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度中的最大值 + 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數(shù)組中的最大值
int res = 0;
for(int n : dp){
if(res < n){
res = n;
}
}
return res;
}
}
- 時(shí)間復(fù)雜度:O(n^2)才睹，n為數(shù)組中的元素
- 空間復(fù)雜度：O(n)徘跪，使用長(zhǎng)度為 n的 dp數(shù)組保存子問題結(jié)果
152. 乘積最大子數(shù)組
問題描述
給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字）琅攘，并返回該子數(shù)組所對(duì)應(yīng)的乘積垮庐。
解題思路
由于此題數(shù)組中的元素既可能是正數(shù)（與正數(shù)相乘的數(shù)越大得到的乘積越大），也可能為負(fù)數(shù)（與負(fù)數(shù)的數(shù)越小得到的乘積才越大）
因此維護(hù)一個(gè)二維的dp數(shù)組存儲(chǔ)以nums[i]結(jié)尾的最大/最小連續(xù)子數(shù)組乘積坞琴；
代碼實(shí)現(xiàn)1-動(dòng)態(tài)規(guī)劃
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
//dp[i][0]表示以nums[i]結(jié)尾的最小連續(xù)子數(shù)組乘積
//dp[i][1]表示以nums[i]結(jié)尾的最大連續(xù)子數(shù)組乘積
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;
}
}
- 時(shí)間復(fù)雜度：O(n)哨查，n為數(shù)組中的元素
- 空間復(fù)雜度：O(n)，n為數(shù)組中的元素
上面的代碼剧辐，在狀態(tài)轉(zhuǎn)移時(shí)寒亥，dp[i]只與dp[i-1]相關(guān)，因此荧关，可以進(jìn)行“狀態(tài)壓縮”溉奕，用變量來代替dp數(shù)組，降低空間復(fù)雜度忍啤。
代碼實(shí)現(xiàn)-壓縮空間
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;
}
}
