常規(guī)動(dòng)態(tài)規(guī)劃問題
相關(guān)題目：
70.爬樓梯
描述
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
分析
當(dāng)n=0，F(xiàn)(n)=0；當(dāng)n=1，F(xiàn)(n)=1；當(dāng)n=2，F(xiàn)(n)=2；
當(dāng)n>=3時(shí)，對(duì)于到達(dá)這個(gè)高度有兩種選擇：1.從n-1處爬1階；2.從n-2處爬2階，
所以F(n)=F(n-1)+F(n-2)。
實(shí)現(xiàn)
public int climbStairs(int n) {
if(n<=2){
return n;
}
int[] memo=new int[n+1];
memo[1]=1;
memo[2]=2;
for(int i =3;i<=n;i++){
memo[i]=memo[i-1]+memo[i-2];
}
return memo[n];
}
發(fā)現(xiàn)重疊子問題
相關(guān)題目：
343.整數(shù)拆分
描述
給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。
示例 1:
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
說明: 你可以假設(shè) n 不小于 2 且不大于 58。
實(shí)現(xiàn)
//記憶化搜索
private int[] memo;
public int integerBreak(int n) {
assert n>=2;
memo=new int[n+1];
return breakInteger(n);
}
private int breakInteger(int n){
if (n==1){
return 1;
}
//記錄分割結(jié)果的最大值
int res=-1;
if (memo[n]!=0){
res=memo[n];
}else {
//從1到n-1計(jì)算分割結(jié)果
for (int i = 1; i <= n - 1; i++) {
res = max3(res, i * (n - i), i * breakInteger(n - i));
}
memo[n]=res;
}
return res;
}
private int max3(int a,int b,int c){
return Math.max(a,Math.max(b,c));
}
public int integerBreak(int n) {
assert n>=2;
memo=new int[n+1];
return breakInteger2(n);
}
private int breakInteger(int n){
memo[1]=1;
for (int i = 2; i <=n ; i++) {
for (int j = 1; j <=i ; j++) {
//將i分割成j+(i-j)
memo[i]= max3(memo[i],j*(i-j),j*memo[i-j]);
}
}
return memo[n];
}
279.完全平方數(shù)
描述
給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。
示例 1:
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
示例 2:
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.
分析
定義一個(gè)函數(shù)f(n)表示我們要求的解。f(n)的求解過程為：
f(n) = 1 + min{
f(n-1^2), f(n-2^2), f(n-3^2), f(n-4^2), ... , f(n-k^2) //(k為滿足k^2<=n的最大的k)
}
實(shí)現(xiàn)
public int numSquares(int n){
if (n==0){
return 0;
}
memo=new int[n+1];
Arrays.fill(memo,Integer.MAX_VALUE);
memo[0]=0;
for (int i = 1; i <= n; i++) {
for (int j = 1; i-j*j>=0 ; j++) {
memo[i]=Math.min(memo[i],1+memo[i-j*j]);
}
}
return memo[n];
}
91.解碼方法
描述
一條包含字母 A-Z 的消息通過以下方式進(jìn)行了編碼：
'A' -> 1
'B' -> 2
...
'Z' -> 26
給定一個(gè)只包含數(shù)字的非空字符串，請(qǐng)計(jì)算解碼方法的總數(shù)。
示例 1:
輸入: "12"
輸出: 2
解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。
示例 2:
輸入: "226"
輸出: 3
解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
分析
思路()：
- s[i]是編碼、s[i-1]是編碼、s[i-1:i+1]是編碼。nums[i] = nums[i-1] + nums[i-2]
- s[i]是編碼、s[i-1]不是編碼。nums[i] = nums[i-1]
- s[i]不是編碼、s[i-1]是編碼、s[i-1:i+1]是編碼。nums[i] = nums[i-2]
- s[i]不是編碼、s[i-1]是編碼、s[i-1:i+1]不是編碼。nums[i] = 0
- 都不是編碼。nums[i] = 0
實(shí)現(xiàn)
public int numDecodings(String s) {
int n = s.length();
if (n==0){
return 0;
}
//memo[i]表示字符串s中下標(biāo)為(i-1)的解碼方法次數(shù)
int[] memo=new int[n+1];
memo[0]=1;
if (s.charAt(0)>'0'){
memo[1]=1;
}
char[] chars = s.toCharArray();
for (int i = 2; i <= n; i++) {
int one = chars[i-1]-'0';
//如果一個(gè)字符滿足(1-9)則記錄
if (one>0){
memo[i]+=memo[i-1];
}
int two = 10*(chars[i-2]-'0')+(chars[i-1]-'0');
//如果兩個(gè)字符滿足(10-26)則記錄
if (two <= 26 && two >= 10) {
memo[i] += memo[i - 2];
}
}
return memo[n];
}
62.不同路徑
描述
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑？
例如，上圖是一個(gè)3 x 7 的網(wǎng)格。有多少可能的路徑？
說明：m 和 n 的值均不超過 100。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
分析
F(i , j)：到達(dá)位置為(i,j)有F(i , j)條路徑。
對(duì)于上邊界的所有點(diǎn)，只有可能從其左邊移動(dòng)過來，那么F(i , j)均為1；同理對(duì)于左邊界上的所有點(diǎn)，
F(i , j)也均為1。
對(duì)于其他的點(diǎn)，都有兩種可能：一是從上方移動(dòng)過來的，二是從左邊移動(dòng)過來的。那么到達(dá)該位置的路徑數(shù)為上方和左方位置之和，因?yàn)樯戏胶妥蠓骄傻竭_(dá)當(dāng)前位置，那么路徑數(shù)是可以累加的。那么F(i , j)=F(I-1,j)+F(i,j-1)。
實(shí)現(xiàn)
public int uniquePaths(int m, int n) {
int[][] memo=new int[m][n];
//初始化左邊界
for(int i=0;i<m;i++){
memo[i][0]=1;
}
//初始化上邊界
for(int i=0;i<n;i++){
memo[0][i]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
//累加上方和左方的路徑數(shù)
memo[i][j]=memo[i-1][j]+memo[i][j-1];
}
}
return memo[m-1][n-1];
}
63.不同路徑(2)
描述
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會(huì)有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。
說明：m 和 n 的值均不超過 100。
示例 1:
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
分析
這一題和上一題的不同在于存在障礙物，那么對(duì)于障礙物的處理是關(guān)鍵：
對(duì)于上邊界的點(diǎn)，若當(dāng)前位置不是障礙物則置為1，若是障礙物，從當(dāng)前位置到結(jié)尾均為0。因?yàn)槠瘘c(diǎn)無法到達(dá)該位置以及以后的位置。
對(duì)于左邊界，也是同理，同樣地處理障礙物。
對(duì)于其他位置，若當(dāng)前位置不是障礙物，則和上題同樣是左邊位置和上邊位置之和；若是障礙物，則直接置為0，因?yàn)椴豢蛇_(dá)。
實(shí)現(xiàn)
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.length;
if(m==0){
return 0;
}
int n = obstacleGrid[0].length;
int[][] memo=new int[m][n];
//初始化左邊界
for(int i=0;i<m;i++){
if(obstacleGrid[i][0]!=1){
memo[i][0]=1;
}else{
//直接跳出，其后的值則均為0
break;
}
}
//初始化上邊界
for(int i=0;i<n;i++){
if(obstacleGrid[0][i]!=1){
memo[0][i]=1;
}else{
break;
}
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
//對(duì)于當(dāng)前位置不是障礙物時(shí)
if(obstacleGrid[i][j]!=1){
memo[i][j]=memo[i-1][j]+memo[i][j-1];
}
}
}
return memo[m-1][n-1];
}
狀態(tài)的定義和狀態(tài)轉(zhuǎn)移
相關(guān)題目：
198.打家劫舍
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2:
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。
分析
狀態(tài)轉(zhuǎn)移方程：F(i)表示在位置i的最大收益。由于不能在相鄰房屋同時(shí)進(jìn)行偷盜，所以對(duì)于每個(gè)位置有兩種選擇，要么偷，要么不偷。
i=0, F(0)=v[0];
i=1,F(1)=max{v[0],v[1]};
那么對(duì)于i>=2, F(i)=max{F(i-1),F(i-2)+v[i]}；
實(shí)現(xiàn)
public int rob(int[] nums) {
int n = nums.length;
if(n==0){
return 0;
}
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0],nums[1]);
}
int[] memo = new int[n];
memo[0]=nums[0];
memo[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<n;i++){
memo[i]=Math.max(memo[i-1],nums[i]+memo[i-2]);
}
return memo[n-1];
}
0-1背包問題
描述
有一個(gè)容量為 C 的背包，要用這個(gè)背包裝下物品的價(jià)值最大，這些物品有兩個(gè)屬性：體積 w和價(jià)值 v。
數(shù)組w中各元素表示每個(gè)物品的重量為w[i]，數(shù)組v中各元素表示每個(gè)物品的價(jià)值為v[i]。
示例：
v={60,100,120};
w={10,20,30};
C=50;
結(jié)果為：220
解釋：20+30<=50,100+120=220
分析
狀態(tài)轉(zhuǎn)移方程：F（i,j）表示擁有前i個(gè)物品，容量為j的背包的價(jià)值最大值。
對(duì)于第i件物品：
能夠放入：在不放入當(dāng)前物品和放入當(dāng)前物品（當(dāng)前背包容量會(huì)減少）中選擇最大值
F(i,j)=max{F(i-1,j),v[i] + F(i-1,j-w[i])}
不能夠放入:F(i,j)=F(i-1,j)
例如：
有一個(gè)容量為5的背包，物品如下所示：
| id | 0 | 1 | 2 |
|---|---|---|---|
| weight | 1 | 2 | 3 |
| value | 6 | 10 | 12 |
表格中的值表示F（i，j）
| id（i）\capcaity（j） | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 6 | 6 | 6 | 6 | 6 |
| 1 | 0 | 6 | 10 | 6+10 | 6+10 | 6+10 |
| 2 | 0 | 6 | 10 | 6+10 | 6+12 | 10+12 |
那么結(jié)果為22
實(shí)現(xiàn)
//時(shí)間復(fù)雜度O(N*C)
//空間復(fù)雜度O(N*C)
public int knapsack(int[] w, int[] v, int C){
int n = w.length;
if (n==0||C==0){
return 0;
}
int[][] memo=new int[n][C+1];
//先初始化
for (int i = 0; i <= C; i++) {
if (i>=w[0]){
memo[0][i]=v[0];
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= C; j++) {
//0：不放入該物品
memo[i][j]=memo[i-1][j];
if (j>=w[i]){
//1：放入該物品
memo[i][j]=Math.max(memo[i-1][j],v[i]+memo[i-1][j-w[i]]);
}
}
}
return memo[n-1][C];
}
空間優(yōu)化：
觀察狀態(tài)轉(zhuǎn)移方程：F(i,j)=max{F(i-1,j),v[i] + F(i-1,j-w[i])}，第i行元素只依賴于第i-1行元素。理論上，只需要保持兩行元素，只需要使用上邊和左邊的元素，使用前后一對(duì)奇偶數(shù)即可。
//優(yōu)化空間復(fù)雜度
//空間復(fù)雜度：O(2*C)
public int knapsack(int[] w, int[] v, int C){
int n = w.length;
if (n==0||C==0){
return 0;
}
memo=new int[2][C+1];
//先初始化
for (int i = 0; i <= C; i++) {
if (i>=w[0]){
memo[0][i]=v[0];
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= C; j++) {
//0：不放入該物品
memo[i%2][j]=memo[(i-1)%2][j];
if (j>=w[i]){
//1：放入該物品
memo[i%2][j]=Math.max(memo[i%2][j],v[i]+memo[(i-1)%2][j-w[i]]);
}
}
}
return memo[(n-1)%2][C];
}
進(jìn)一步優(yōu)化空間：
因?yàn)?dp[j-w] 表示 dp[i-1] [j-w]，因此不能先求 dp[i] [j-w]，以防將 dp[i-1] [j-w] 覆蓋。也就是說要先計(jì)算 dp[i] [j] 再計(jì)算 dp[i] [j-w[i]]，在程序?qū)崿F(xiàn)時(shí)需要按倒序來循環(huán)求解。
private int[] dp;
//進(jìn)一步優(yōu)化空間復(fù)雜度
//空間復(fù)雜度：O(C)
public int knapsack2(int[] w, int[] v, int C){
int n = w.length;
if (n==0||C==0){
return 0;
}
dp=new int[C+1];
//先初始化，將第一個(gè)元素放入背包中
for (int i = 0; i <= C; i++) {
if (i>=w[0]){
dp[i]=v[0];
}
}
for (int i = 1; i < n; i++) {
//從右向左
for (int j = C; j >=w[i] ; j--) {
dp[j]=Math.max(dp[j],v[i]+dp[j-w[i]]);
}
}
return dp[C];
}
416.分割等和子集
描述
給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
注意:
每個(gè)數(shù)組中的元素不會(huì)超過 100
數(shù)組的大小不會(huì)超過 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組不能分割成兩個(gè)元素和相等的子集.
分析
這道題其實(shí)可以變成是0-1背包問題，申請(qǐng)二維數(shù)組dp[i] [j]（0<=i<=nums.size()，0<=j<=(sum/2)，sum是數(shù)組的和），要?jiǎng)澐殖蓛砂肭液拖嗟龋磗um(left)=sum(right)，那么原數(shù)組和必須是偶數(shù)，否則無法劃分。其中dp[i] [j]表示從第一個(gè)元素到第i個(gè)元素是否存在能組成和為j的子集，如果可以為true，否則為false。
接下來我們來看遞推公式，看看dp[i][j]可以怎么由子問題推導(dǎo)而來，先給出公式：
dp[i] [j] = dp[i - 1] [j] || dp[i - 1] [j - nums[i]];
- 如果考慮第i個(gè)元素，那么情況等于前i-1個(gè)元素的子集和加上第i個(gè)元素的和可以組成和j，j-nums[i]表示前i-1個(gè)元素可以組成和為j-nums[i]，那么加上第i個(gè)元素nums[i]，和即為j，可以組成子集。
- 如果不考慮第i個(gè)元素，那么情況等于前i-1個(gè)元素的情況即dp[i-1] [j]（前i-1個(gè)元素如果已經(jīng)可以劃分子集左，那么剩下的元素直接劃分到另外一邊即子集右即可）
所以是這兩種情況的或構(gòu)成遞推公式，我一直覺得這道題和背包問題的理解有點(diǎn)出入，因?yàn)?-1背包問題是背或者不背，但一定所有的元素最后都會(huì)有結(jié)果（背或者不背），而這道題元素的背指的在左半邊子集，不背指的在右半邊子集，我們的目標(biāo)是使得左半邊子集的和等于總和的一半。這樣思考才會(huì)和背包問題對(duì)應(yīng)上。
實(shí)現(xiàn)
二維數(shù)組：
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum=0;
for(int i:nums){
sum+=i;
}
if(sum%2!=0){
return false;
}
sum/=2;
boolean[][] memo=new boolean[n+1][sum+1];
for(int i=1;i<n+1;i++){
memo[i][0]=true;
}
for(int i=1;i<n+1;i++){
for(int j=1;j<sum+1;j++){
if(j>=nums[i-1]){
memo[i][j]=memo[i-1][j]||memo[i-1][j-nums[i-1]];
}else{
memo[i][j]=memo[i-1][j];
}
}
}
return memo[n][sum];
}
一維數(shù)組：
public boolean canPartition(int[] nums){
int n = nums.length;
if (nums==null||n==0){
return false;
}
int sum=0;
for (int i = 0; i <n ; i++) {
sum+=nums[i];
}
if (sum%2!=0){
return false;
}
int c=sum/2;
int[] dp=new boolean[c+1];
for (int i = 0; i <= c; i++) {
dp[i]=(nums[0]==i);
}
for (int i = 1; i < n; i++) {
for (int j = c; j >=nums[i] ; j--) {
dp[j]=dp[j]||dp[j-nums[i]];
}
}
return dp[c];
}
0-1背包問題的變種
- 完全背包問題：每個(gè)物品可以無限使用
- 多維費(fèi)用背包問題：要考慮物品的體積和重量兩個(gè)維度？三維數(shù)組實(shí)現(xiàn)
- 物品之間可以有互相排斥；也可以互相依賴
完全背包問題
377.組合總和（4）
描述
給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)。
示例:
nums = [1, 2, 3]
target = 4
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請(qǐng)注意，順序不同的序列被視作不同的組合。
因此輸出為 7。
進(jìn)階：
如果給定的數(shù)組中含有負(fù)數(shù)會(huì)怎么樣？
問題會(huì)產(chǎn)生什么變化？
我們需要在題目中添加什么限制來允許負(fù)數(shù)的出現(xiàn)？
分析
由于數(shù)組中的每個(gè)元素可以選擇多次，所以該題為完全背包問題，其中target為容量。
dp[i]：表示和為i從數(shù)組nums中選擇的組合數(shù)
舉例：nums=[1,2,3], target=4
dp[1]=dp[0]=1
dp[2]=dp[1]+dp[0]=2
dp[3]=dp[2]+dp[1]+dp[0]=4
dp[4]=dp[3]+dp[2]+dp[1]=7
實(shí)現(xiàn)
private int[] dp;
public int combinationSum4(int[] nums, int target){
int c=target;
int n=nums.length;
if (n==0){
return 0;
}
//dp[i]:表示和為i的組合次數(shù)
dp=new int[c+1];
//和為0的組合次數(shù)只有一種
dp[0]=1;
//dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+...
for (int i = 1; i <=c ; i++) {
for (int j = 0; j < n; j++) {
if (i>=nums[j]){
dp[i]+=dp[i-nums[j]];
}
}
}
return dp[c];
}
139.單詞拆分
描述
給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。
說明：
拆分時(shí)可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復(fù)使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
分析
由于字典中的元素的使用次數(shù)不限制，那么這是一個(gè)完全背包問題。
dp[i]表示字符串s[0...i)是否存在于字典中。
如果S能夠被“字典集合”（dict）中的單詞拼接而成，所以滿足下列方程：
狀態(tài)轉(zhuǎn)移方程：
f(0)=true,表示空
f(i)=f(j)&&dict.contains(s[j,i))，0<j<i，確保了s[0,j)和s[j,i)均存在于字典中
實(shí)現(xiàn)
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
if (n==0){
return false;
}
memo=new boolean[n+1];
memo[0]=true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
String tStr = s.substring(j, i);
if (memo[j]&&wordDict.contains(tStr)){
memo[i]=true;
break;
}
}
}
return memo[n];
}
322.零錢兌換
描述
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的。
分析
由于每種硬幣的數(shù)量是無限的，那么這一題就是一道完全背包問題。
狀態(tài)轉(zhuǎn)移方程：
F(i,j)表示使用從下標(biāo)為0到(i-1)的元素累計(jì)總金額為j時(shí)的最少硬幣數(shù)量
F(i,j)=min{F(i-1,j),F(i,j-coins[i])+1}
實(shí)現(xiàn)
二維數(shù)組：
public int coinChange(int[] coins, int amount) {
int n = coins.length;
if(n==0){
return 0;
}
/*F(i,j)=min{F(i-1,j),F(i,j-coins[i])+1}*/
//memo[i][j]：表示使用從下標(biāo)為0到(i-1)的元素累加和為j時(shí)的最少硬幣數(shù)量
int[][] memo=new int[n+1][amount+1];
//初始化
for (int i = 0; i < amount+1; i++) {
memo[0][i] = amount+1;
}
for (int i = 0; i < n; i++) {
memo[i][0] = 0;
}
for(int i=1;i<n+1;i++){
for(int j=1;j<amount+1;j++){
if(j>=coins[i-1]){
//memo[i][j-coins[i-1]]+1中i體現(xiàn)出了每個(gè)硬幣可以使用多次，即完全背包特性
memo[i][j]=Math.min(memo[i-1][j],memo[i][j-coins[i-1]]+1);
}else{
memo[i][j]=memo[i-1][j];
}
}
}
int res=memo[n][amount]==(amount+1)?-1:memo[n][amount];
return res;
}
一維數(shù)組：
public int coinChange(int[] coins, int amount) {
//memo[i]：累加金額為i使用的最少硬幣數(shù)量
int[] memo=new int[amount+1];
Arrays.fill(memo,amount+1);
memo[0]=0;
for (int coin:coins){
for (int i = coin; i <=amount; i++) {
memo[i]=Math.min(memo[i],memo[i-coin]+1);
}
}
if (memo[amount]==amount+1){
memo[amount]=-1;
}
return memo[amount];
}
0-1背包變種
474.一和零
描述
在計(jì)算機(jī)界中，我們總是追求用有限的資源獲取最大的收益。
現(xiàn)在，假設(shè)你分別支配著 m 個(gè) 0 和 n 個(gè) 1。另外，還有一個(gè)僅包含 0 和 1 字符串的數(shù)組。
你的任務(wù)是使用給定的 m 個(gè) 0 和 n 個(gè) 1 ，找到能拼出存在于數(shù)組中的字符串的最大數(shù)量。每個(gè) 0 和 1 至多被使用一次。
注意:
給定 0 和 1 的數(shù)量都不會(huì)超過 100。
給定字符串?dāng)?shù)組的長度不會(huì)超過 600。
示例 1:
輸入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
輸出: 4
解釋: 總共 4 個(gè)字符串可以通過 5 個(gè) 0 和 3 個(gè) 1 拼出，即 "10","0001","1","0" 。
示例 2:
輸入: Array = {"10", "0", "1"}, m = 1, n = 1
輸出: 2
解釋: 你可以拼出 "10"，但之后就沒有剩余數(shù)字了。更好的選擇是拼出 "0" 和 "1" 。
分析
二維背包，1和0的數(shù)量相當(dāng)于背包容量。memo[i] [j]表示0的個(gè)數(shù)為i，1的個(gè)數(shù)為j能拼出字符串的最大數(shù)量。
考慮兩種情況：
- 使用當(dāng)前字符串（背上該物品），在0的數(shù)量為i-count0(count0:當(dāng)前字符串0的個(gè)數(shù))，1的數(shù)量為j-count1(count1:當(dāng)前字符串1的個(gè)數(shù))的基礎(chǔ)上再加一。
- 不使用當(dāng)前字符串（不背該物品）
實(shí)現(xiàn)
private int[][] memo;
public int findMaxForm(String[] strs, int m, int n) {
memo=new int[m+1][n+1];
for (String str:strs){
int count0=0;
int count1=0;
char[] chars = str.toCharArray();
for (int i = 0; i <chars.length ; i++) {
if (chars[i]=='0'){
count0++;
}
if (chars[i]=='1'){
count1++;
}
}
for (int i = m; i >=count0 ; i--) {
for (int j = n; j >=count1 ; j--) {
memo[i][j]=Math.max(memo[i][j],memo[i-count0][j-count1]+1);
}
}
}
return memo[m][n];
}
494.目標(biāo)和
描述
給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)，S?，F(xiàn)在你有兩個(gè)符號(hào) + 和 -。對(duì)于數(shù)組中的任意一個(gè)整數(shù)，你都可以從 + 或 -中選擇一個(gè)符號(hào)添加在前面。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。
示例 1:
輸入: nums: [1, 1, 1, 1, 1], S: 3
輸出: 5
解釋:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5種方法讓最終目標(biāo)和為3。
注意:
數(shù)組的長度不會(huì)超過20，并且數(shù)組中的值全為正數(shù)。
初始的數(shù)組的和不會(huì)超過1000。
保證返回的最終結(jié)果為32位整數(shù)。
分析
sum(P)表示所有正數(shù)的和，sum(N)表示所有負(fù)數(shù)的絕對(duì)值之和。
sum(P)-sum(N)=S
sum(nums)=sum(P)+sum(N)
-->S+sum(nums)=2sum(P)
? -->sum(P)=(S+sum(nums))/2
這樣就在該數(shù)組中尋找和為sum(P)的最大方式數(shù)，即有多少種方式使得元素之和為sum(P)。
因?yàn)閷?duì)于數(shù)組中的每個(gè)元素，都有兩種選擇，要么取，要么不取。這樣就轉(zhuǎn)化成為了0-1背包問題，其中背包的容量為sum(P)。
實(shí)現(xiàn)
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
if (n==0){
return 0;
}
int sum=0;
for (int i = 0; i < n; i++) {
sum+=nums[i];
}
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
int p=(sum+S)/2;
//memo[i]:和為i最多有多少種方式
int[] memo=new int[p+1];
//和為0的情況只有一種，那就是所有元素均不取
memo[0]=1;
//對(duì)于每一個(gè)元素都有不取和取兩種選擇
for(int i=0;i<n;i++){
for(int j=p;j>=nums[i];j--){
memo[j]=memo[j]+ memo[j-nums[i]];
}
}
return memo[p];
}
LIC(最長上升子序列)
相關(guān)問題：
674.最長連續(xù)遞增子序列
描述
給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組，找到最長且連續(xù)的的遞增序列。
示例 1:
輸入: [1,3,5,4,7]
輸出: 3
解釋: 最長連續(xù)遞增序列是 [1,3,5], 長度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?和7在原數(shù)組里被4隔開。
示例 2:
輸入: [2,2,2,2,2]
輸出: 1
解釋: 最長連續(xù)遞增序列是 [2], 長度為1。
注意：數(shù)組長度不會(huì)超過10000。
分析
由于是連續(xù)遞增子序列，所以只需要檢查相鄰的元素之間的大小關(guān)系即可。利用一個(gè)len記錄以當(dāng)前元素結(jié)尾的連續(xù)遞增子序列的長度，maxLen記錄最長連續(xù)遞增子序列的長度，即取len中的最大值。
實(shí)現(xiàn)
public int findLengthOfLCIS(int[] nums) {
int n = nums.length;
if(n==0){
return 0;
}
int maxLen=1;
int len=1;
for(int i=1;i<n;i++){
if(nums[i]>nums[i-1]){
len++;
maxLen=Math.max(maxLen,len);
}else{
len=1;
}
}
return maxLen;
}
300.最長上升子序列
描述
給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明:
可能會(huì)有多種最長上升子序列的組合，你只需要輸出對(duì)應(yīng)的長度即可，子序列不要求連續(xù)。
你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?
分析
- DP：
LIS(i)表示以第i個(gè)數(shù)字為結(jié)尾的最長上升子序列的長度，即[0,..,i]的范圍內(nèi)，選擇數(shù)字nums[i]可以獲得的最長上升子序列的長度。
LIS(i) = max(1+LIS(j) if nums[i]>nums[j])，j<i
- 二分搜索：
memo[i]: 所有長度為i+1的遞增子序列中, 最小的那個(gè)序列尾數(shù).
由定義知memo數(shù)組必然是一個(gè)遞增數(shù)組, 可以用 max 來表示最長遞增子序列的長度.
對(duì)數(shù)組進(jìn)行迭代, 依次判斷每個(gè)數(shù)num將其插入memo數(shù)組相應(yīng)的位置:
1. num > memo[maxL], 表示num比所有已知遞增序列的尾數(shù)都大, 將num添加入數(shù)組
數(shù)組尾部, 并將最長遞增序列長度max加1
2. memo[i-1] < num <= memo[i], 只更新相應(yīng)的memo[i]
實(shí)現(xiàn)
DP解法：
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n==0){
return 0;
}
//memo[i]:表示數(shù)組nums中以下標(biāo)為i的元素為結(jié)尾的上升序列的長度
int[] memo=new int[n];
Arrays.fill(memo,1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j]<nums[i]){
memo[i]=Math.max(memo[i],memo[j]+1);
}
}
}
int max=1;
for (int i = 0; i < n; i++) {
max=Math.max(max,memo[i]);
}
return max;
}
二分查找解法：
public int lengthOfLIS(int[] nums){
int maxLen=0;
//存儲(chǔ)著所有長度為i+1的遞增子序列中, 最小的那個(gè)序列尾數(shù)
//memo[]必然為遞增數(shù)組
int[] memo=new int[nums.length];
for (int num:nums){
int l=0,h=maxLen;
while (l<h){
int mid=l+(h-l)/2;
if (memo[mid]<num) l=mid+1;
else h=mid;
}
//將對(duì)應(yīng)的數(shù)字放入相應(yīng)的位置上
memo[l]=num;
//表示num比所有已知遞增序列的尾數(shù)都大，則數(shù)組拓展的時(shí)候
if (l==maxLen){
maxLen++;
}
}
return maxLen;
}
354.俄羅斯套娃問題
描述
給定一些標(biāo)記了寬度和高度的信封，寬度和高度以整數(shù)對(duì)形式 (w, h) 出現(xiàn)。當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，
這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。
請(qǐng)計(jì)算最多能有多少個(gè)信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
說明:
不允許旋轉(zhuǎn)信封。
示例:
輸入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出: 3
解釋: 最多信封的個(gè)數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
分析
- 動(dòng)態(tài)規(guī)劃：
首先將所有信封按照width和height的升序排列，即先按照width升序，若width相等則按照height的升序排列。這樣就轉(zhuǎn)化成為了LIC（最長上升子序列）問題。
memo[i]，表示以第i個(gè)元素結(jié)尾的信封的最大套娃（即width和height均遞增的序列）的長度。
- 二分搜索：
首先先按照width升序排列，如果width相等就按照height降序排列，這樣可以保證依次遍歷數(shù)組的時(shí)候，保證若height大于前面的元素的height，width必定大于該元素的width，這樣就一定可以包含前面的這個(gè)元素。這樣就轉(zhuǎn)化成了一位數(shù)組的LIS問題,即尋找height的最長上升子序列。
實(shí)現(xiàn)
DP解法（效率蠻低的）：
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
if (n==0){
return 0;
}
int[] memo=new int[n];
Arrays.fill(memo,1);
Arrays.sort(envelopes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0]!=o2[0]){
return o1[0]-o2[0];
}else {
return o1[1]-o2[1];
}
}
});
int max=1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1]){
memo[i]=Math.max(memo[i],memo[j]+1);
}
max=Math.max(memo[i],max);
}
}
return max;
}
二分查找解法：
public int maxEnvelopes(int[][] envelopes){
int n = envelopes.length;
if (n==0){
return 0;
}
int len=0;
int[] memo=new int[n];
Arrays.sort(envelopes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0]==o2[0]){
return o2[1]-o1[1];
}
return o1[0]-o2[0];
}
});
for (int[] envelope:envelopes){
int l=0,h=len-1;
while (l<=h){
int mid=l+(h-l)/2;
if (envelope[1]>memo[mid]) l=mid+1;
else h=mid-1;
}
memo[l]=envelope[1];
if (l==len){
len++;
}
}
return len;
}
376.擺動(dòng)序列
描述
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱為擺動(dòng)序列。第一個(gè)差（如果存在的話）可能是正數(shù)或負(fù)數(shù)。少于兩個(gè)元素的序列也是擺動(dòng)序列。
例如， [1,7,4,9,2,5] 是一個(gè)擺動(dòng)序列，因?yàn)椴钪?(6,-3,5,-7,3) 是正負(fù)交替出現(xiàn)的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零。
給定一個(gè)整數(shù)序列，返回作為擺動(dòng)序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。
示例 1:
輸入: [1,7,4,9,2,5]
輸出: 6
解釋: 整個(gè)序列均為擺動(dòng)序列。
示例 2:
輸入: [1,17,5,10,13,15,10,5,16,8]
輸出: 7
解釋: 這個(gè)序列包含幾個(gè)長度為 7 擺動(dòng)序列，其中一個(gè)可為[1,17,10,13,10,16,8]。
示例 3:
輸入: [1,2,3,4,5,6,7,8,9]
輸出: 2
進(jìn)階:
你能否用 O(n) 時(shí)間復(fù)雜度完成此題?
分析
使用用up[i]和down[i]分別記錄以第i個(gè)元素為結(jié)尾為上升沿和下降沿結(jié)束的最長擺動(dòng)序列長度
實(shí)現(xiàn)
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n==0||n==1){
return n;
}
int[] up=new int[n];
int[] down=new int[n];
up[0]=1;
down[0]=1;
for (int i = 1; i < n; i++) {
if (nums[i]>nums[i-1]){
//上升的時(shí)候，因?yàn)槭菙[動(dòng)序列，所以u(píng)p[i]可以在上一個(gè)下降沿的基礎(chǔ)上增加，當(dāng)前位置的下降沿保持不變
up[i]=down[i-1]+1;
down[i]=down[i-1];
}else if (nums[i]<nums[i-1]){
//下降的時(shí)候
down[i]=up[i-1]+1;
up[i]=up[i-1];
}else {
down[i]=down[i-1];
up[i]=up[i-1];
}
}
return Math.max(up[n-1],down[n-1]);
}
LCS（最長公共子序列）
描述
給出兩個(gè)字符串S1和S2，求這兩個(gè)字符串的最長公共子序列的長度？
分析
LCS(m,n)表示S1[0...m]和S2[0...n]的最長公共子序列的長度，對(duì)于每個(gè)元素有以下兩種情況：
- S1[m]==S2[n]：LCS(m,n)=1+LCS(m-1,n-1)
- S1[m]!=S2[n]：LCS(m,n)=max{LCS(m,n-1),LCS(m,n-1)}
實(shí)現(xiàn)
public int lengthOfLCS(String s1,String s2){
int m = s1.length();
int n = s2.length();
if(m==0||n==0){
return 0;
}
int[][] memo = new int[m+1][n+1];
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(chars1[i-1]==chars2[j-1]){
memo[i][j]=1+memo[i-1][j-1];
}else{
memo[i][j]=Math.max(memo[i-1][j],memo[i][j-1]);
}
}
}
int len = memo[m][n];
return len;
}
股票交易問題
121.買賣股票的最佳時(shí)機(jī)
描述
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。
注意你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
分析
由于本題目中限制最多只能做一筆交易，那么只需要設(shè)置兩個(gè)變量：
- hold：若持有當(dāng)前股票時(shí)候的最大利潤（由于只能做一筆交易，所以在本題中hold一定為負(fù)數(shù)，即最小成本）
- unhold：若拋售當(dāng)前股票時(shí)候的最大利潤
實(shí)現(xiàn)
public int maxProfit(int[] prices) {
int n = prices.length;
if (n==0){
return 0;
}
//持有股票
int hold=Integer.MIN_VALUE;
//拋售股票
int unhold=0;
for (int i = 0; i < n; i++) {
hold=Math.max(hold,-prices[i]);
unhold=Math.max(unhold,hold+prices[i]);
}
return unhold;
}
122.買賣股票的最佳時(shí)機(jī)(2)
描述
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
分析
由于可以盡可能多地做交易，那么可以看作交易次數(shù)不限制的股票交易問題。
這里可以使用貪心算法，每當(dāng)有股票上升就進(jìn)行交易。
實(shí)現(xiàn)
//貪心策略：只要有上升就進(jìn)行交易
public int maxProfit(int[] prices) {
int n = prices.length;
if (n==0||n==1){
return 0;
}
int max=0;
for (int i = 1; i < n; i++) {
if (prices[i]>prices[i-1]){
max+=prices[i]-prices[i-1];
}
}
return max;
}
123.買賣股票的最佳時(shí)機(jī)(3)
描述
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意: 你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價(jià)格 = 0）的時(shí)候買入，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
隨后，在第 7 天（股票價(jià)格 = 1）的時(shí)候買入，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這個(gè)情況下, 沒有交易完成, 所以最大利潤為 0。
分析
由于本題最多只能做兩次交易，那么需要設(shè)置兩對(duì)變量：
- hold1,unhold1：第一次的交易；
- hold2,unhold2：第二次的交易，在第一次的基礎(chǔ)上。
實(shí)現(xiàn)
public int maxProfit(int[] prices) {
int n=prices.length;
if (n==0||n==1){
return 0;
}
//第一次交易
int hold1=Integer.MIN_VALUE;
int unhold1=0;
//第二次交易
int hold2=Integer.MIN_VALUE;
int unhold2=0;
for (int i = 0; i < n; i++) {
hold1=Math.max(hold1,-prices[i]);
unhold1=Math.max(unhold1,hold1+prices[i]);
hold2=Math.max(hold2,unhold1-prices[i]);
unhold2=Math.max(unhold2,hold2+prices[i]);
}
return unhold2;
}
188.買賣股票的最佳時(shí)機(jī)(4)
描述
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
注意: 你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [2,4,1], k = 2
輸出: 2
解釋: 在第 1 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2:
輸入: [3,2,6,5,0,3], k = 2
輸出: 7
解釋: 在第 2 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。
隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。
分析
由于本題目中最多可以做k次交易，那么對(duì)于k的大小應(yīng)該分情況討論：
- 當(dāng)k>=n/2,那么相當(dāng)于可以做無限次交易，即轉(zhuǎn)化為121題n為股票的總數(shù)即總天數(shù)；
- 當(dāng)k<n/2，設(shè)置兩個(gè)數(shù)組用來分別記錄這k次交易的hold和unhold
實(shí)現(xiàn)
//122題+123題
public int maxProfit(int k, int[] prices) {
int n=prices.length;
if (n==0||n==1||k==0){
return 0;
}
//當(dāng)2k>n,相當(dāng)于可以進(jìn)行不限次數(shù)的交易
//退化為122題
if (k>n/2){
return maxProfit(prices);
}
int[] holds=new int[k];
int[] unholds=new int[k];
Arrays.fill(holds,Integer.MIN_VALUE);
Arrays.fill(unholds,0);
for (int i = 0; i < n; i++) {
//做K次交易，注意第一次交易hold的初始值為0
for (int j = 0; j < k; j++) {
unholds[j] = Math.max(unholds[j], holds[j] + prices[i]);
if (j==0){
holds[j]=Math.max(holds[j],-prices[i]);
}else {
holds[j] = Math.max(holds[j], unholds[j-1] - prices[i]);
}
}
}
return Math.max(unholds[k-1],holds[k-1]);
}
private int maxProfit(int[] prices){
int n=prices.length;
if (n==0||n==1){
return 0;
}
int res=0;
for (int i = 1; i <n ; i++) {
if (prices[i]>prices[i-1]){
res+=prices[i]-prices[i-1];
}
}
return res;
}
309.買賣股票時(shí)機(jī)含冷凍期
描述
給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 。?
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
分析
交易次數(shù)沒有限制，由于由冷卻期的限制，那么在每次持有股票的時(shí)候可以是沒有買入或買入兩種狀態(tài)，每當(dāng)買入的時(shí)候前面一定有個(gè)冷卻期,對(duì)于i>2的時(shí)候：
hold(i)=max{hold(i-1),unhold(i-2)-prices[i]}
對(duì)于不持有股票的時(shí)候可以是沒有賣出和賣出兩種狀態(tài)：
unhold(i)=max{unhold(i-1),hold(i-1)+prices[i]}
實(shí)現(xiàn)
public int maxProfit(int[] prices) {
int n=prices.length;
if (n<=1){
return 0;
}
int[] hold=new int[n]; //hold[i]:第i天持有股票的最大收益
int[] unhold=new int[n]; //unhold[i]:第i天不持有股票的最大收益
hold[0]=-prices[0];
hold[1]=Math.max(hold[0],-prices[1]);
unhold[0]=0; //第一天不能拋售股票
unhold[1]=Math.max(unhold[0],hold[0]+prices[1]);
for (int i = 2; i < n; i++) {
//沒有買入和買入
hold[i] = Math.max(hold[i-1], unhold[i-2] - prices[i]);
//沒有賣出和賣出
unhold[i] = Math.max(unhold[i-1], hold[i-1] + prices[i]);
}
return unhold[n-1];
}
714.買賣股票時(shí)機(jī)含手續(xù)費(fèi)
描述
給定一個(gè)整數(shù)數(shù)組 prices，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。
你可以無限次地完成交易，但是你每次交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值。
示例 1:
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達(dá)到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
分析
本題交易次數(shù)沒有限制，多了一個(gè)限制在于交易費(fèi)，其操作和309題中操作是類似的，但是沒有冷卻期，并且每次拋售的時(shí)候需要扣除交易費(fèi)用。
實(shí)現(xiàn)
public int maxProfit(int[] prices, int fee) {
int n=prices.length;
if (n==0||n==1){
return 0;
}
int[] hold=new int[n];
int[] unhold=new int[n];
hold[0]=-prices[0];
hold[1]=Math.max(-prices[0],-prices[1]);
for (int i = 1; i <n ; i++) {
hold[i]=Math.max(unhold[i-1]-prices[i],hold[i-1]);
//拋售的時(shí)候扣除交易費(fèi)用
unhold[i]=Math.max(hold[i-1]+prices[i]-fee,unhold[i-1]);
}
return Math.max(hold[n-1],unhold[n-1]);
}
更多動(dòng)態(tài)規(guī)劃的問題
5.最長回文子串
描述
給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
分析
- DP：狀態(tài)轉(zhuǎn)移方程為F(i,j)表示下標(biāo)為i和j之間的字符是否能夠組成回文串，
若s[i]==s[j]并且F(i+1,j-1)，表示能夠構(gòu)成新的回文串，這時(shí)F(i,j)=true
否則，均不能構(gòu)成回文串
-
中心拓展法：回文串分為兩種，一種為奇數(shù)個(gè)，另一種為偶數(shù)個(gè)。把每個(gè)字母當(dāng)成回文串的中心
這里要考慮兩種情況，回文串的長度為奇數(shù)或者偶數(shù)情況。
實(shí)現(xiàn)
解法1：動(dòng)態(tài)規(guī)劃
public String longestPalindrome(String s) {
int n = s.length();
if (n==0){
return "";
}
//記錄最長的回文串的起始下標(biāo)
int start=0;
//記錄最長回文串的長度
int maxLen=1;
//memo[i][j] i:起始下標(biāo)，j：結(jié)束下標(biāo)，表示是否為回文串
boolean[][] memo=new boolean[n][n];
char[] chars = s.toCharArray();
//初始化，需要將相鄰位置初始化
for (int i = 0; i < n; i++) {
memo[i][i]=true;
if (i+1<n&&chars[i]==chars[i+1]){
memo[i][i+1]=true;
maxLen=2;
start=i;
}
}
//若s[i]和s[j]相等，并且memo[i+1][j-1]為true，此時(shí)可以構(gòu)建新的回文串s[i,j],這時(shí)只能構(gòu)建偶數(shù)回文串，從后向前地搜索
for (int i = n-1; i >= 0; i--) {
for (int j = i+2; j <n ; j++) {
if (chars[i]==chars[j]&&memo[i+1][j-1]){
memo[i][j]=true;
if (j-i+1>maxLen){
maxLen=j-i+1;
start=i;
}
}
}
}
return s.substring(start,start+maxLen);
}
解法2：
String res="";
public String longestPalindrome(String s){
if (s==null||s.length()==0){
return "";
}
for (int i = 0; i < s.length(); i++) {
expand(s, i, i); //回文串長度為奇數(shù)
expand(s, i, i + 1); //回文串長度為偶數(shù)
}
return res;
}
//從中間開始拓展
private void expand(String s, int l , int r){
while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
l--;
r++;
}
//由于跳出循環(huán)的時(shí)候, l--和r++各多執(zhí)行了一次 所以需要 l + 1回來 r - 1 回來， 然后r 需要+ 1 所以不用變
String cur=s.substring(l+1,r);
if (cur.length()>res.length()){
res=cur;
}
}
53.最大子序和
描述
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
實(shí)現(xiàn)
public int maxSubArray(int[] nums){
//全局最大值
int max=nums[0];
//局部最大值:當(dāng)前的連續(xù)子序和
int curMax=nums[0];
for (int i = 1; i < nums.length; i++) {
//繼續(xù)累加
if (curMax>=0){
curMax+=nums[i];
}else//curMax<0:重新在i位置選擇連續(xù)子數(shù)組
{
curMax=nums[i];
}
//從局部最大值中選擇出全局最大值
max=Math.max(max,curMax);
}
return max;
}
120.三角形最小路徑和
描述
給定一個(gè)三角形，找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。
例如，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個(gè)問題，那么你的算法會(huì)很加分
分析
狀態(tài)轉(zhuǎn)移方程為：
f(0,0)=t[0][0]
- f(i,0)=t[i][0]+f(i-1,0)
- f(i,i)=t[i][i]+f(i-1,i-1)
- f(i,j)=t[i][j]+min{f(i-1,j-1),f(i-1,j)}
實(shí)現(xiàn)
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
if (n==0){
return 0;
}
for (int i = 1; i < n; i++) {
triangle.get(i).set(0,triangle.get(i-1).get(0)+triangle.get(i).get(0));
triangle.get(i).set(i,triangle.get(i).get(i)+triangle.get(i-1).get(i-1));
for (int j = 1; j <i ; j++) {
triangle.get(i).set(j,triangle.get(i).get(j)+Math.min(triangle.get(i-1).get(j-1),triangle.get(i-1).get(j)));
}
}
int min=Integer.MAX_VALUE;
for(int i:triangle.get(n-1)){
min=Math.min(min,i);
}
return min;
}
public int minimumTotal(List<List<Integer>> triangle){
int n = triangle.size();
if (n==0){
return 0;
}
int[] memo=new int[n];
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
if (j==0){
memo[j]+=triangle.get(i).get(0);
}else if (i==j){
memo[j]=triangle.get(i).get(i)+memo[i-1];
}else {
memo[j]=triangle.get(i).get(j)+Math.min(memo[j],memo[j-1]);
}
}
}
for (int i = 0; i < n; i++) {
System.out.print(memo[i]+" ");
}
int min=memo[0];
for (int i = 0; i < n; i++) {
min=Math.min(min,memo[i]);
}
return min;
}
221.最大的正方形
描述
在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形，并返回其面積。
示例:
輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4
實(shí)現(xiàn)
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if (m==0){
return 0;
}
int n = matrix[0].length;
//記錄當(dāng)前位置最大正方形的邊長
int[][] memo = new int[m][n];
//最大正方形的邊長
int res=0;
//初始化上邊緣
for (int i = 0; i < m; i++) {
if (matrix[i][0]=='1'){
memo[i][0]=1;
res=1;
}
}
//初始化左邊緣
for (int i = 0; i < n; i++) {
if (matrix[0][i]=='1'){
memo[0][i]=1;
res=1;
}
}
//狀態(tài)轉(zhuǎn)移方程：F（i,j）=Min{F(i,j-1),F(i-1,j),F(i-1,j-1)}+1
//如果當(dāng)前位置為1，那么當(dāng)前位置的最大正方形的邊長最多比它的上方，左方和左上方的位置多1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j]=='1'){
memo[i][j]=min3(memo[i-1][j],memo[i][j-1],memo[i-1][j-1])+1;
//記錄最大的邊長
res=Math.max(res,memo[i][j]);
}
//else --> matrix[0][i]!='1' { memo[i][j]=0 }
}
}
return res*res;
}
//從三個(gè)數(shù)中獲得最小值
private int min3(int a,int b,int c){
return Math.min(a,Math.min(b,c));
}
