0. 動(dòng)態(tài)規(guī)劃分析
0.1 動(dòng)態(tài)規(guī)劃、遞歸和貪心算法的區(qū)別
動(dòng)態(tài)規(guī)劃就是利用分治思想和解決冗余的辦法來(lái)處理問(wèn)題，所以必然會(huì)有dp數(shù)組來(lái)實(shí)現(xiàn)記憶搜索，從而解決冗余，而分治思想就是遞歸的思想，總的問(wèn)題可以分為若干相同的子問(wèn)題，所有子問(wèn)題的解合并即是該問(wèn)題的解。
遞歸解決問(wèn)題是一個(gè)自頂向下的思路，一直從最大的問(wèn)題（頂）遞歸至小問(wèn)題（下，底），只有小問(wèn)題解決了，一層一層地返回，便可以得到最終的結(jié)果。
動(dòng)態(tài)規(guī)劃解決問(wèn)題是一個(gè)自底而上的思路，從小問(wèn)題（下）開(kāi)始，把小問(wèn)題的計(jì)算結(jié)果保存至dp數(shù)組中，計(jì)算更大的問(wèn)題時(shí)會(huì)用到小問(wèn)題的結(jié)果，直接調(diào)用而不必重新計(jì)算，直到最大問(wèn)題。
貪心算法就是動(dòng)態(tài)規(guī)劃問(wèn)題中的局部最優(yōu)問(wèn)題解，不要遍歷當(dāng)前子問(wèn)題中的所有情況，一般只取當(dāng)前最優(yōu)的情況。
0.2 dp公式
dp[i][j]公式是為了求出當(dāng)前的狀態(tài)，需要再次搜索得到次解的索引，所以有索引變化，就有解的搜索。
所以，動(dòng)態(tài)規(guī)劃問(wèn)題就是需要分析出，當(dāng)前狀態(tài)與前一個(gè)狀態(tài)的對(duì)應(yīng)，即當(dāng)前問(wèn)題的子問(wèn)題的組合
0.3 動(dòng)態(tài)規(guī)劃問(wèn)題的復(fù)雜度
由于動(dòng)態(tài)規(guī)劃一般用兩個(gè)for循環(huán)實(shí)現(xiàn)，所以
時(shí)間復(fù)雜度是O(n^2)或O(mn)
空間復(fù)雜度是O(n^2)或O(n)
所以，一般都不是最好的算法，只是用來(lái)處理可以避免遺漏問(wèn)題解
想要提高算法效率，繼續(xù)抓住問(wèn)題的特點(diǎn)可以找到更多隱藏的信息，提供解題的切入點(diǎn)，得到的效果就會(huì)不一樣。
0.4 動(dòng)態(tài)規(guī)劃問(wèn)題與深度優(yōu)先或廣度優(yōu)先問(wèn)題
動(dòng)態(tài)規(guī)劃問(wèn)題和BFS與DFS問(wèn)題在分析子問(wèn)題時(shí)，有時(shí)候會(huì)遇到相同的子問(wèn)題是類似的情況，總問(wèn)題是多個(gè)子問(wèn)題的綜合，這是共同點(diǎn)
- 動(dòng)態(tài)規(guī)劃是全面處理最優(yōu)問(wèn)題，時(shí)間和空間復(fù)雜度比較大，但是可以優(yōu)化，這是一個(gè)覆蓋全部子問(wèn)題的解決方法，重點(diǎn)是全面和最優(yōu)
- 深度/廣度優(yōu)先遍歷是如何更加高效地處理這個(gè)問(wèn)題，講到的是時(shí)間效率，降低時(shí)間復(fù)雜度，空間復(fù)雜度一般都是指數(shù)遞增的，重點(diǎn)在優(yōu)先
動(dòng)態(tài)規(guī)劃是有最優(yōu)問(wèn)題的，中間的子問(wèn)題也有最優(yōu)解，但是BFS與DFS是求解一個(gè)客觀存在的唯一問(wèn)題。比如，求二叉樹(shù)的最長(zhǎng)深度，這個(gè)是一個(gè)DFS問(wèn)題，雖然有“最”字，但是這個(gè)客觀存儲(chǔ)的，不是最優(yōu)問(wèn)題。比如，求解二叉樹(shù)的最淺分支，這是一個(gè)BFS問(wèn)題，也是客觀存在的，不是子問(wèn)題有選擇的問(wèn)題。
0.5 輔助數(shù)組的作用
一般情況下，我們都會(huì)利用與原問(wèn)題矩陣行列大于1的新數(shù)組來(lái)存儲(chǔ)需要重復(fù)計(jì)算的數(shù)據(jù)，即原問(wèn)題矩陣或數(shù)組分別為arr[n][m]和arr[n]，而輔助數(shù)組為dp[n+1][m+1]和dp[n+1]，目的是計(jì)算arr矩陣中的每一個(gè)位置的對(duì)應(yīng)最優(yōu)解，這就是動(dòng)態(tài)規(guī)劃問(wèn)題的最優(yōu)子問(wèn)題的數(shù)據(jù)存儲(chǔ)地方。
在此求解過(guò)程中，如果我們保持的數(shù)據(jù)只與前面幾個(gè)數(shù)據(jù)有關(guān)，例如跳一步和跳兩步這個(gè)問(wèn)題，下一個(gè)問(wèn)題只與之前的兩個(gè)數(shù)據(jù)有關(guān)，所以交替保存數(shù)據(jù)，只用O(1)空間復(fù)雜度便可以實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃問(wèn)題。
1. （LeetCode） 單個(gè)幣種無(wú)限個(gè)數(shù)的硬幣找零
給你不同面值的硬幣數(shù)組coins和總金額amount。 編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算您需要對(duì)amount金額的進(jìn)行找零的最少數(shù)量的硬幣。 如果這些金額不能由硬幣的任何組合來(lái)找零，則返回'-1'。
例 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
例 2:
coins = [2], amount = 3
return -1.
注意:假設(shè)每一個(gè)幣種的數(shù)量是無(wú)限的
題目分析
理論分析
理論分析是重復(fù)取所有coins，判斷當(dāng)前數(shù)額n可以找零取錢(qián)最少
dp(n) = min{ dp(n - coins[i]) + 1} , i = 0, 1, 2,..., m.
編程實(shí)現(xiàn)分析
每一次取值與已經(jīng)存在的最小F(n)比較，選擇最小的，因?yàn)槲覀冎灰雷钚〉?，中間的數(shù)據(jù)不必保存
dp(n) = min{ dp(n), dp(n - conins[i]) + 1}, i = 0, 1, 2,..., m.
問(wèn)題剖析
由于本問(wèn)題是一個(gè)單個(gè)幣種可以重復(fù)選擇的問(wèn)題，所以這就意味著每取一個(gè)元素，后面可以取的情況與前一次是獨(dú)立的，沒(méi)有關(guān)系，獨(dú)立重復(fù)處理。而對(duì)于給定字符串的組合問(wèn)題，則是取了元素之后，能取的元素就少了一個(gè)。字符串組合和給定全部一個(gè)的幣種的問(wèn)題是一樣的。
當(dāng)前問(wèn)題與上一次遇到的情況是一樣的，如果把每一次取元素當(dāng)作當(dāng)前問(wèn)題，下一次取值就是子問(wèn)題，這種分析問(wèn)題的方式比較容易理解
代碼實(shí)現(xiàn)
public int coinChange(int[] coins, int amount){
if(coins.length < 1 || amount < 1) return -1;
int[] dp = new int[amount + 1];
for(int i = 1; i <= amount; ++i){
dp[i] = amount;
for(int j = 0; j < coins.length; ++j){
if(coins[j] <= i){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1:dp[amount];
}
2.幣種無(wú)限個(gè)數(shù)的硬幣找零組合
給你不同面值的硬幣數(shù)組coins和總金額amount。 編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算組成該amount的組合的數(shù)量。每種硬幣的個(gè)數(shù)是無(wú)限的。
注意：假設(shè)
- 0 <= amount <= 5000
- 1 <= coin <= 5000
- the number of coins is less than 500
- the answer is guaranteed to fit into signed 32-bit integer
例 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
有四種組合方式：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
例2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
例 3:
Input: amount = 10, coins = [10]
Output: 1
代碼分析
求種類數(shù)，多少種方法，多少條路徑等這類問(wèn)題
只要開(kāi)頭走到結(jié)尾就算1種（1次），所以共有多少種方法，就是看分叉的次數(shù)，分叉次數(shù)就是總和。
代碼實(shí)現(xiàn)
public class Solution {
public int change(int amount, int[] coins) {
int[] dp=new int[amount+1];
dp[0]=1;
for(int i=0;i<coins.length;i++){
for(int j=0;j<amount+1;j++){
if(j-coins[i]>=0){
dp[j]+=dp[j-coins[i]];
}
}
}
return dp[amount];
}
}
3.回文子串問(wèn)題
3.1 Palindromic Substrings
題目描述
給定一個(gè)字符串，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串。
具有不同起始索引或結(jié)束索引的子字符串即使由相同的字符組成，也會(huì)被計(jì)為不同的子字符串。
例1：
輸入： “abc”
輸出： 3
說(shuō)明：三個(gè)回文串：“a”，“b”，“c”。
例2：
輸入： “aaa”
輸出： 6
說(shuō)明：六個(gè)回文串：“a”，“a”，“a”，“aa”，“aa”，“aaa”。
代碼實(shí)現(xiàn)
public int countSubstrings(String s) {
int n = s.length();
int res = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
if(dp[i][j]) ++res;
}
}
return res;
}
復(fù)雜度更好的算法[1]
3.2 Longest Palindromic Substring
問(wèn)題描述
給定一個(gè)字符串s，找到s中的最長(zhǎng)回文子串。假設(shè)s的最大長(zhǎng)度是1000。
例1：
輸入： “babad”
輸出： “bab”
注意： “aba”也是一個(gè)有效的答案。
例2：
輸入： “cbbd”
輸出： “bb”
思路分析
dp[i][j] 的定義如下面的公式：
則遞歸公式：
編程實(shí)現(xiàn)過(guò)程
輸入:BCDFDECB
輸出：DFD
代碼實(shí)現(xiàn)
public String longestPalindrome(String s) {
int n = s.length();
String res = null;
boolean[][] dp = new boolean[n][n];
//依次從最后面進(jìn)行迭代，前一輪迭代為可能的回文的第一個(gè)字符，然后依次進(jìn)行比對(duì)是否與第一個(gè)字符相等，如果不等則直接為False，然后進(jìn)行后續(xù)比對(duì)，如果找到相同的字符，則比對(duì)左斜下的子字符的回文信息，由于i+1，j-1，所以開(kāi)始比對(duì)的是第i-1和第j-1字符是否相等，依次向里面靠攏，直到相遇。
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) { //dp[i+1][j-1]是一個(gè)左斜下的小回文
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);// j-i<3是在只有三個(gè)字符或四個(gè)字符為回文時(shí)的快速判斷，不需要獲取左斜下對(duì)角的值
if (dp[i][j] && (res == null || j - i + 1 > res.length())) { //找出比之前更長(zhǎng)的回文，則更新字符串
res = s.substring(i, j + 1);
}
}
}
return res;
}
復(fù)雜度
Time complexity : O(n^2)
Space complexity : O(n^2)
復(fù)雜度更好的算法[2]
4.背包問(wèn)題
4.1 背包問(wèn)題的特點(diǎn)
給定了一個(gè)固定的容量結(jié)果數(shù)，計(jì)算最優(yōu)解并且限制條件是這個(gè)固定容量
Max f(x)
s.t. w <= W
4.2 問(wèn)題描述
有N件物品，每件物品的體積為W1，W2……Wn（Wi為整數(shù)），與之相對(duì)應(yīng)的價(jià)值為P1,P2……Pn（Pi為整數(shù)），現(xiàn)在從中取出若干件物品放入容量為W的背包里。求背包能夠裝下的最大價(jià)值。
4.3 題目分析
實(shí)現(xiàn)固定體積裝下最大價(jià)值的方法：
1.從物品索引開(kāi)始，依次選擇取本物品或不取物品。
2.對(duì)待第一個(gè)是這樣，對(duì)待第二物品也是選擇或不選擇
3.選擇或不選擇，還有一個(gè)判斷條件，就是選擇的本物品的體積不能大于當(dāng)前背包的剩余的空間
所以，本質(zhì)上也是一個(gè)組合問(wèn)題！從n個(gè)物品中選擇m（m的取值從0至n）個(gè)，使m個(gè)物品的價(jià)值之和最大，這個(gè)最大就是最優(yōu)問(wèn)題。
4.4 上述分析的編程結(jié)果分析
依次分析結(jié)果，W1,W1W2,W2,W1W2W3,W2W3,...,Wn。
但是在中間由于增加了一個(gè)最優(yōu)解，所以利用O(1)的空間復(fù)雜度就可以保存之前遍歷的組合的最大價(jià)值。
4.5 代碼實(shí)現(xiàn)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] dp = new int[v + 1];
int[] price = new int[n + 1];
int[] weight = new int[n + 1];
long max = 0;
for (int i = 1; i < n + 1; i++) {
weight[i] = in.nextInt();
price[i] = in.nextInt();
}
for (int i = 1; i < n + 1; i++)
for (int j = v; j > 0; j--)
if (j - weight[i] >= 0)
dp[j] = Math.max(dp[j], dp[j - weight[i]] + price[i]);
else
dp[j] = dp[j];
for (int i = 0; i < v + 1; i++)
max = max > dp[i] ? max : dp[i];
System.out.println(max);
}
}
5. Integer Break
本問(wèn)題與背包問(wèn)題也是一樣的，分裂固定的總數(shù)，使相乘結(jié)果最優(yōu)。
題目描述
給定一個(gè)正整數(shù)n，將其分解為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。返回您可以獲得的最大產(chǎn)品。
例如，給定n = 2，返回1（2 = 1 + 1）; 給定n = 10，返回36（10 = 3 + 3 + 4）。
注意：你可以假設(shè)n不小于2且不大于58。
題目分析
數(shù)學(xué)的分析[1]:大于4的自然數(shù)，每次乘以3便可以，小于4的數(shù)枚舉便可。
例如：
dp[8] = dp[3] * dp[3] * dp[2]
dp[11] = dp[3] * dp[8]
dp[4] = dp[2] * dp[2]
所以取值問(wèn)題是盡量讓被分的數(shù)離3接近，如果dp[2] * dp[2] > dp[3] * dp[1]
代碼實(shí)現(xiàn)
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 1; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}
5.Perfect Squares
問(wèn)題描述
給定一個(gè)正整數(shù)n，找到與1, 4, 9, 16, ...相加的和為n的最小完美平方數(shù)。
例如，給定n = 12，返回3,因?yàn)?code>12 = 4 + 4 + 4; 給n = 13，返回2,因?yàn)?code>13 = 4 + 9。
問(wèn)題分析
這實(shí)際上是一個(gè)背包問(wèn)題的改進(jìn)，每次減去的是一個(gè)數(shù)的平方（j^2），然后計(jì)算最小的減法操作次數(shù)
背包問(wèn)題與零錢(qián)找零問(wèn)題也是類似的，所以統(tǒng)稱為“背包問(wèn)題”
代碼實(shí)現(xiàn)
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
++j;
}
dp[i] = min;
}
return dp[n];
}
6. 字符串的距離和編輯問(wèn)題
問(wèn)題描述
對(duì)于序列S和T，它們之間距離定義為：
對(duì)二者其一進(jìn)行幾次以下的操作
(1)刪去一個(gè)字符；
(2)插入一個(gè)字符；
(3)改變一個(gè)字符。
每進(jìn)行上面任意一次操作，計(jì)數(shù)增加1。
將S和T變?yōu)橥粋€(gè)字符串的最小計(jì)數(shù)即為它們的距離（最優(yōu)問(wèn)題）
問(wèn)題的遞歸思路分析
說(shuō)明：dp[i][j] 表示截取字符S和T在第i和第j個(gè)字符之前的字符進(jìn)行比對(duì)，這個(gè)相對(duì)于拿整個(gè)字符來(lái)處理，是子問(wèn)題。
1.從兩個(gè)字符串尾字符開(kāi)始建立索引并向前走，如果兩個(gè)字符相等則dp[i][j] = dp[i-1][j-1]
2.如果兩個(gè)字符不等，則從三種選擇中選擇一種操作進(jìn)行本次更改（以下b和c中有多個(gè)重復(fù)的情況）：
(a)修改S或T的這個(gè)字符，讓其等于另外一個(gè)字符，相等后就表示兩個(gè)字符相等了，也就是第一種情況，但操作了一回，所以為dp[i][j] = dp[i-1][j-1] + 1
(b)刪除S或T的這個(gè)字符，然后進(jìn)行下一次比較，此時(shí)這兩個(gè)字符還是不等于，也就回到了下一次比較的情況，同時(shí)比較刪除S中這個(gè)不等的字符得到的結(jié)果與刪除T中的這個(gè)字符得到的結(jié)果，取小的，如dp[i][j] = min{ dp[i-1][j] + 1, dp[i][j-1] + 1 }
(c)在S或T中插入一個(gè)字符讓這兩個(gè)字符相等，同時(shí)比較插入到S后的結(jié)果與插入到T中的結(jié)果，取小的，如dp[i][j] = min{ dp[i][j-1] + 1, dp[i-1][j] + 1 }
3.第二步的三種不相等情況綜合結(jié)果，再取最小值就是本次處理不相等的情況，dp[i][j] = min{ dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1 }
代碼實(shí)現(xiàn)
利用for循環(huán)把遞歸思路轉(zhuǎn)化為非遞歸思路,重點(diǎn)理解for循環(huán)迭代實(shí)現(xiàn)了遞歸中的思路，注意for循環(huán)中的全部步驟為什么可以覆蓋這個(gè)問(wèn)題的全部情況
public static int similarityString(String s, String t) {
if(sLen == 0) return tLen;
if(tLen == 0) return sLen;
int sLen = s.length();
int tLen = t.length();
int i,j;
char ch1,ch2;
int cost;
int[][] dp = new int[sLen + 1][tLen + 1];
//下面兩個(gè)是邊界條件
for(i = 0; i <= sLen; i++) dp[i][0] = i; //這里是有意義的，就是當(dāng)一個(gè)字符串長(zhǎng)度為0，這就意味著另外一個(gè)字符串必須全部刪除
for(i = 0; i <= tLen; i++) dp[0][i] = i ;
for(i = 1; i < = sLen; i++) { //第一個(gè)for循環(huán)表示第一個(gè)字符串取其前i個(gè)字符
ch1 = s.charAt(i - 1);
for(j = 1; j <= tLen; j++) { // 第二個(gè)for循環(huán)表示第二個(gè)字符串取其前j個(gè)字符
ch2 = t.charAt(j - 1);
if(ch1 == ch2) cost = 0;
else cost = 1;
dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),dp[i - 1][j - 1] + cost);
}
}
return dp[sLen][tLen];
}
7. 最長(zhǎng)公共子序列(Longest Common Subsequence,LCS)
問(wèn)題描述
對(duì)于序列S和T，求它們的最長(zhǎng)公共子序列的長(zhǎng)度。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}則它們的lcs是{B,C,B,A}和{B,D,A,B}，所以結(jié)果為4.
題目分析
dp[i][j] 表示取字符串S的第i個(gè)字符之前的序列和T的第j個(gè)字符之前的序列進(jìn)行比對(duì)，求其最長(zhǎng)子序列的長(zhǎng)度。
1.從尾部字符開(kāi)始取起，如果S和T字符串的字符相等，則dp[i][j] = dp[i-1][j-1] + 1.
2.如果S和T字符串的字符不相等，則比較以下兩種情況，取其中的最大值
(a)留下S的字符，去掉T的字符，利用S當(dāng)前字符與T的第j-1字符進(jìn)行比較，dp[i][j] = dp[i][j-1]
(b)去掉S的字符，留下T的字符，利用S的前一個(gè)字符i-1字符與T的當(dāng)前j字符進(jìn)行比較，dp[i][j] = dp[i-1][j]
3.每進(jìn)行一次取元素的時(shí)候，遇到的問(wèn)題又與上一次遇到的情況是一樣的，所以遞歸就可以實(shí)現(xiàn)。
代碼實(shí)現(xiàn)
public static int compute(char[] str1, char[] str2){
int substringLength1 = str1.length;
int substringLength2 = str2.length;
// 構(gòu)造二維數(shù)組記錄子問(wèn)題A[i]和B[j]的LCS的長(zhǎng)度
int[][] dp = new int[substringLength1 + 1][substringLength2 + 1];
// 從后向前，動(dòng)態(tài)規(guī)劃計(jì)算所有子問(wèn)題。也可從前到后。
for (int i = substringLength1 - 1; i >= 0; i--){
for (int j = substringLength2 - 1; j >= 0; j--){
if (str1[i] == str2[j])
dp[i][j] = dp[i + 1][j + 1] + 1;// 狀態(tài)轉(zhuǎn)移方程
else
//索引加的不同，表示參考基準(zhǔn)不同
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);// 狀態(tài)轉(zhuǎn)移方程
}
}
System.out.println("substring1:" + new String(str1));
System.out.println("substring2:" + new String(str2));
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2){
if (str1[i] == str2[j]){
System.out.print(str1[i]); //逐個(gè)輸出最長(zhǎng)公共子串
i++; j++;
}
else if (dp[i + 1][j] >= dp[i][j + 1]) i++;
else j++;
}
System.out.println();
return dp[0][0]; //最長(zhǎng)公共子串的長(zhǎng)度
}
8. Maximal Square
題目描述
給定一個(gè)只包含0和1的矩陣，找到只包含1的最大方陣并返回其面積。
例如，給出以下矩陣：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
返回4。
題目分析
初始化另一個(gè)矩陣（dp），其尺寸與初始化為0的所有矩陣相同。
dp（i，j）表示右下角是原始矩陣中索引為（i，j）的單元格的最大方格的邊長(zhǎng)。
從索引（0,0）開(kāi)始，對(duì)于在原始矩陣中找到的每個(gè)1元素，我們將當(dāng)前元素的值更新為
代碼實(shí)現(xiàn)
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int[][] dp = new int[rows + 1][cols + 1];
int maxsqlen = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i-1][j-1] == '1'){
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
maxsqlen = Math.max(maxsqlen, dp[i][j]);
}
}
}
return maxsqlen * maxsqlen;
}
}
9.House Robber
問(wèn)題描述
假如你是一名專業(yè)的強(qiáng)盜，計(jì)劃搶劫沿街的房屋。每間房屋都藏有一定數(shù)量的金錢(qián)，但是同一晚上有兩間相鄰的房屋被闖入，它將自動(dòng)觸發(fā)警報(bào)。
輸入一個(gè)代表每個(gè)房屋的金額的非負(fù)整數(shù)列表，在沒(méi)有觸發(fā)警報(bào)的情況下，輸出你搶劫的最高金額。
代碼實(shí)現(xiàn)
class Solution {
public int rob(int[] nums){
if(nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
if(nums.length < 2) return dp[nums.length -1];
for(int i = 2; i < n; i++){
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n];
}
}
10.Maximum Subarray
問(wèn)題描述
在數(shù)組中找到連續(xù)的子數(shù)組（至少包含一個(gè)數(shù)字），使這個(gè)子數(shù)組的總和最大。
例如，給定數(shù)組[-2,1,-3,4,-1,2,1,-5,4]，
連續(xù)子數(shù)組[4,-1,2,1]的最大sum = 6.
代碼實(shí)現(xiàn)
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
11.Range Sum Query - Immutable
問(wèn)題描述
給定一個(gè)整數(shù)數(shù)組NUMS，找到索引（i,j）之間的元素的總和，包括端值。
例：
給定nums = [-2，0，3，-5，2，-1]
sumRange（0，2） - > 1
sumRange（2，5） - > -1
sumRange（0，5） - > -3
注意：
- 這個(gè)數(shù)組不能改變。
- 可能會(huì)有很多次sumRange函數(shù)調(diào)用。
代碼實(shí)現(xiàn)
public class NumArray {
private int[] sums; /dp數(shù)組
public NumArray(int[] nums) {
if(nums.length != 0){
sums = new int[nums.length];
sums[0] = nums[0];
for(int i=1; i<nums.length; i++){
sums[i] = nums[i] + sums[i-1];
}
}
}
public int sumRange(int i, int j) {
return i==0 ? sums[j] : sums[j]-sums[i-1];
}
}
12.Unique Substrings in Wraparound String
題目描述
將字符串s作為“abcdefghijklmnopqrstuvwxyz”的無(wú)限循環(huán)·字符串，因此s將如下所示：“... zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd ....”。
現(xiàn)有另一個(gè)字符串p，請(qǐng)找出有多少個(gè)唯一的非空子串p存在于字符串s中。
注意： p只包含小寫(xiě)英文字母，p的大小可能超過(guò)10000。
例1：
輸入： “a”
輸出： 1
說(shuō)明：字符串“s”中只有字符串“a”的子串“s”。
例2：
輸入： “cac”
輸出： 2
說(shuō)明：字符串s中有兩個(gè)字符串“cac”的子字符串“a”，“c”。
例3：
輸入： “zab”
輸出： 6
說(shuō)明：字符串s中的字符串“zab”有六個(gè)子字符串“z”，“a”，“b”，“za”，“ab”，“zab”。
本例的特別說(shuō)明
本例其實(shí)是順序組合問(wèn)題，除了位置不變，還有不能任意取不相鄰的元素組合在一起，這種組合就是簡(jiǎn)單的相加就可以實(shí)現(xiàn)總數(shù)了。
例如， 字符abcd的本例組合，a,b,c,d,ab,bc,cd,abc,bcd,abcd共10個(gè)，實(shí)際上sum = 1+2+3+4,有幾個(gè)就是幾個(gè)的加法運(yùn)算。
代碼實(shí)現(xiàn)
public class Solution {
public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26]; //容量只有26的散列表，用于dp輔助數(shù)組，實(shí)現(xiàn)最優(yōu)子問(wèn)題
// store longest contiguous substring ends at current position.
int maxLengthCur = 0;
for (int i = 0; i < p.length(); i++) {
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25)))
maxLengthCur++;
else
maxLengthCur = 1;
int index = p.charAt(i) - 'a'; //判斷當(dāng)前字符是那個(gè)字母
count[index] = Math.max(count[index], maxLengthCur); //更新字符中的數(shù)據(jù)，如果連續(xù)字符越長(zhǎng)，數(shù)字越大，例如abcdfe, abcdef，其中前面的e和f為1，而后面字符串的e和f為5和6
}
// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
}
13.Maximum Product Subarray
問(wèn)題描述
在數(shù)組中找到連續(xù)的子數(shù)組（至少包含一個(gè)數(shù)字），使該數(shù)組中包含最大的產(chǎn)品（相乘為最大）。
例如，給定數(shù)組[2,3,-2,4]，則連續(xù)的子數(shù)組[2,3]具有最大的product = 2*3= 6。
給定數(shù)組[2,3,-2,-1],則連續(xù)的子數(shù)組為[2,3,-2,-1]，product = 12.
代碼實(shí)現(xiàn)
public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[] f = new int[A.length];
int[] g = new int[A.length]; //用來(lái)存儲(chǔ)最小值，因?yàn)橛锌赡苡卸鄠€(gè)復(fù)數(shù)
f[0] = A[0];
g[0] = A[0];
int res = A[0];
for (int i = 1; i < A.length; i++) {
f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
res = Math.max(res, f[i]);
}
return res;
}
}
空間復(fù)雜度更好的代碼
int maxProduct(int A[], int n) {
// store the result that is the max we have found so far
int r = A[0];
// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (A[i] < 0)
swap(imax, imin);
// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);
// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}
14.Unique Paths
題目描述
機(jī)器人位于一個(gè)m x n網(wǎng)格的左上角（在下圖中標(biāo)記為“start”）。
機(jī)器人只能隨時(shí)向下或向右移動(dòng)。機(jī)器人正在嘗試到達(dá)網(wǎng)格的右下角（在下圖中標(biāo)記為“finish”）。
有多少可能的獨(dú)特路徑？
代碼實(shí)現(xiàn)（O(n*m)空間復(fù)雜度）
標(biāo)準(zhǔn)的方式，計(jì)算每一個(gè)位置的信息，這種方式可以完整的記憶內(nèi)容，但是如果不需要就浪費(fèi)空間了
class Solution {
int uniquePaths(int m, int n) {
vector<vector<int> > path(m, vector<int> (n, 1));
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
path[i][j] = path[i - 1][j] + path[i][j - 1];
return path[m - 1][n - 1];
}
};
代碼實(shí)現(xiàn)（O[min(n,m)]空間復(fù)雜度）
因?yàn)槲覀冎灰喇?dāng)前列或前一列的信息就夠了
class Solution {
int uniquePaths(int m, int n) {
if (m > n) return uniquePaths(n, m);
vector<int> pre(m, 1);
vector<int> cur(m, 1);
for (int j = 1; j < n; j++) {
for (int i = 1; i < m; i++)
cur[i] = cur[i - 1] + pre[i];
swap(pre, cur);
}
return pre[m - 1];
}
};
15.Create Maximum Number
題目描述
給定兩個(gè)長(zhǎng)度數(shù)組m和n數(shù)字0-9代表兩個(gè)數(shù)字。k <= m + n從兩個(gè)數(shù)字中創(chuàng)建最大長(zhǎng)度數(shù)。必須保留來(lái)自同一陣列的數(shù)字的相對(duì)順序。返回k數(shù)字的數(shù)組。您應(yīng)該嘗試優(yōu)化算法的時(shí)間和空間復(fù)雜性。
例1：
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
返回[9, 8, 6, 5, 3]
例2：
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
返回[6, 7, 6, 0, 4]
例3：
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
返回[9, 8, 9]
題目分析
本題的情況是從兩個(gè)數(shù)組中找到子數(shù)組使結(jié)果順序最大值，其實(shí)本題有點(diǎn)類似于歸并排序問(wèn)題，但是由于保持原來(lái)的順序，并且從中只選取k個(gè)數(shù)據(jù)，所以特點(diǎn)又有點(diǎn)不一樣。
代碼實(shí)現(xiàn)
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int m = nums2.length;
int[] ans = new int[k];
//在兩個(gè)數(shù)組中選擇i個(gè)數(shù)據(jù)和k-i個(gè)數(shù)據(jù)，然后找出對(duì)應(yīng)數(shù)組中的i個(gè)或k-i個(gè)最大順序數(shù)據(jù)
for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (greater(candidate, 0, ans, 0)) ans = candidate;
}
return ans;
}
//合并從兩個(gè)數(shù)組中選取數(shù)據(jù)，大的放入ans數(shù)組中，這也是因?yàn)闅w并排序?yàn)榉€(wěn)定排序的原因可以實(shí)現(xiàn)此算法
private int[] merge(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
for (int i = 0, j = 0, r = 0; r < k; ++r)
ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
return ans;
}
//比較兩個(gè)數(shù)組在相同索引位置上的值，那個(gè)大，[4,3,2,1]>[4,3,1,1]
public boolean greater(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
//選擇數(shù)組中的k個(gè)最大數(shù)據(jù)，注意這里的k個(gè)要與數(shù)組的個(gè)數(shù)比對(duì)，如果k=數(shù)組長(zhǎng)度，則全部取值，否則在當(dāng)前索引后面的個(gè)數(shù)還大于k個(gè)的時(shí)候，我們先取最大值。
//比如，[3,4,6,1]取兩個(gè)，則先取3，如果3當(dāng)前的索引后面還有多余2個(gè)的數(shù)據(jù)，當(dāng)前索引為0，后面還有3個(gè)，所以比較3和4，大的放入ans數(shù)組中，后面是4小于6，取6，此時(shí)ans=[6,]，后面只有一個(gè)數(shù)據(jù)了，所以不管多大，取值后ans=[6,1]
public int[] maxArray(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[k];
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
if (j < k) ans[j++] = nums[i];
}
return ans;
}
復(fù)雜度
在最壞的情況下，算法的時(shí)間復(fù)雜度為O((m + n）^ 3）
16.Longest Valid Parentheses
題目描述
給定一個(gè)只包含字符'('和')'的字符串，找出最長(zhǎng)且有效的括號(hào)子字符串的長(zhǎng)度。
"(()"最長(zhǎng)的有效括號(hào)子字符串"()"長(zhǎng)度= 2。
而)()())"最長(zhǎng)的有效括號(hào)子字符串"()()"，其長(zhǎng)度= 4。
代碼實(shí)現(xiàn)
class Solution {
public int longestValidParentheses(String s) {
if(s.length() <= 0) return 0;
Stack<Integer> stack = new Stack<Integer>(); //保存'('的索引位置
int max = 0; //記錄最大長(zhǎng)度
int leftIndex = -1; //記錄stack加入'('的初始位置
for(int i = 0; i < s.length(); ++i){
if(s.charAt(i) == '(') stack.push(i);
else{
if(stack.isEmpty()) leftIndex = i;//如果第一個(gè)字符為')'時(shí)，會(huì)出現(xiàn)前面為空的情況，例如")()'
else{
stack.pop(); //只要不為空，則必然之前壓入了'('，先依次計(jì)算最近距離，然后繼續(xù)彈出，看是否還有'('，則繼續(xù)拿當(dāng)前字符索引減去stack中的值
if(stack.isEmpty()) max = Math.max(max, i - leftIndex);//如果為空了，則只能減去保存在leftIndex中的值，因?yàn)槟莻€(gè)是起點(diǎn)
else max = Math.max(max, i - stack.peek()); //如果不為空則，表示之前還有'('
}
}
}
return max;
}
}
參考文獻(xiàn)
[1] leetcode 518. Coin Change 2
[2] 跳臺(tái)階
[4] 變態(tài)跳臺(tái)階
[5] java 動(dòng)態(tài)規(guī)劃策略原理及例題(很詳細(xì)）
