總結(jié)：https://labuladong.gitbook.io/algo/
最長回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring/
給定一個(gè)字符串 s物延，找到 s 中最長的回文子串宣旱。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案叛薯。
示例 2：
輸入: "cbbd"
輸出: "bb"
動(dòng)態(tài)規(guī)劃解法
我們用 P(i,j) 表示字符串 s 的第 i 到 j 個(gè)字母組成的串是否為回文串浑吟；那么我們就可以寫出動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程：
也就是說笙纤，只有 s[i+1:j-1]是回文串，并且 s 的第 i 和 j 個(gè)字母相同時(shí)组力，s[i:j] 才會(huì)是回文串省容。
上文的所有討論是建立在子串長度大于 2 的前提之上的，我們還需要考慮動(dòng)態(tài)規(guī)劃中的邊界條件燎字，即子串的長度為 1或 2腥椒。對(duì)于長度為 1 的子串，它顯然是個(gè)回文串轩触；對(duì)于長度為 2 的子串寞酿，只要它的兩個(gè)字母相同家夺，它就是一個(gè)回文串脱柱。因此我們就可以寫出動(dòng)態(tài)規(guī)劃的邊界條件：
根據(jù)這個(gè)思路，我們就可以完成動(dòng)態(tài)規(guī)劃了拉馋，最終的答案即為所有 P(i,j)=true 中 j?i+1（即子串長度）的最大值榨为。
注意：在狀態(tài)轉(zhuǎn)移方程中，我們是從長度較短的字符串向長度較長的字符串進(jìn)行轉(zhuǎn)移的煌茴，因此一定要注意動(dòng)態(tài)規(guī)劃的循環(huán)順序随闺。程序中我們使用d表示子字符串的長度，作為第一層循環(huán)的變量蔓腐，從小到大逐漸增加矩乐；
public static String longestPalindrome(String s) {
int n = s.length();
boolean[][] P = new boolean[n][n];
if (n <= 1) {
return s;
}
int maxLen = 1;
String maxStr = s.substring(0, 1);
// 初始化(邊界條件)
for (int i = 0; i < n; i++) {
P[i][i] = true;
if (i < n - 1) {
P[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
if (P[i][i + 1]) {
maxLen = 2;
maxStr = s.substring(i, i + 2);
}
}
}
// 動(dòng)態(tài)規(guī)劃
for (int d = 2; d <= n - 1; d++) {
for (int L = 0; L < n - d; L++) {
int R = L + d;
P[L][R] = P[L + 1][R - 1] & (s.charAt(L) == s.charAt(R));
if (P[L][R]) {
int len = R - L + 1;
if (len > maxLen) {
maxStr = s.substring(L, R + 1);
maxLen = len;
}
}
}
}
return maxStr;
}
中心擴(kuò)散法
遍歷所有可能出現(xiàn)的回文子串的“中心位置”，從“中心位置”嘗試盡可能擴(kuò)散出去回论，得到一個(gè)回文串散罕。
枚舉“中心位置”時(shí)間復(fù)雜度為 O(N)，從“中心位置”擴(kuò)散得到“回文子串”的時(shí)間復(fù)雜度為 O(N)傀蓉，因此時(shí)間復(fù)雜度為欧漱。
在這里要注意一個(gè)細(xì)節(jié)：回文串在長度為奇數(shù)和偶數(shù)的時(shí)候，“回文中心”的形式是不一樣的葬燎。
奇數(shù)回文串的“中心”是一個(gè)具體的字符误甚，例如：回文串 "aba" 的中心是字符 "b"；
偶數(shù)回文串的“中心”是位于中間的兩個(gè)字符的“空隙”谱净，例如：回文串串 "abba" 的中心是兩個(gè) "b" 中間的那個(gè)“空隙”窑邦。
public static String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
int maxLen = 1;
String maxStr = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
String s1 = expand(s, i, i);// aba
String s2 = expand(s, i, i + 1);// abba
String maxLenStr = s1.length() > s2.length() ? s1 : s2;
if (maxLenStr.length() > maxLen) {
maxLen = maxLenStr.length();
maxStr = maxLenStr;
}
}
return maxStr;
}
public static String expand(String s, int L, int R) {
int n = s.length();
while (L >= 0 && L < n && R >= 0 && R < n && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return s.substring(L+1, R);
}
馬拉車算法（Malacher，中心擴(kuò)散算法的改進(jìn)版）
public String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
// 得到預(yù)處理字符串
String newString = preProcess(s);
int newLen = newString.length();
int[] armLen = new int[newLen]; // 記錄已經(jīng)計(jì)算過的回文子串半徑長度信息
int maxRight = 0; // 它是遍歷過的 i 的 i + armLen[i] 的最大者
int maxCenter = 0; // 它是遍歷過的 i 的 i + armLen[i] 的最大者 對(duì)應(yīng)的 i
int oriMaxLen = 1; // 原始字符串的最長回文子串的長度
int oriMaxStart = 0; // 原始字符串的最長回文子串的起始位置
for (int i = 0; i < newLen; i++) {
int offset = 0;
if (i < maxRight) {
int mirror = 2 * maxCenter - i;
offset = Math.min(maxRight - i, armLen[mirror]); // 馬拉車算法的關(guān)鍵, 即每次擴(kuò)散時(shí)不再從center開始, 而是從center +/- armLen開始
}
// 每次擴(kuò)散時(shí)不再從center開始, 而是從center +/- armLen開始
armLen[i] = expand(newString, i, offset);
// 更新maxRight以便最大限度利用已經(jīng)計(jì)算過的回文長度信息
if (i + armLen[i] > maxRight) {
maxRight = i + armLen[i];
maxCenter = i;
}
// 更新原始字符串的最長回文信息
if (armLen[i] > oriMaxLen) {
oriMaxLen = armLen[i];
oriMaxStart = (i - oriMaxLen) / 2;
}
}
return s.substring(oriMaxStart, oriMaxStart + oriMaxLen);
}
private int expand(String s, int center, int offSet) {
int len = s.length();
int i = center - (1 + offSet);
int j = center + (1 + offSet);
int armLen = offSet;
while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
i--;
j++;
armLen++;
}
return armLen;
}
private String preProcess(String s){
StringBuilder newSB = new StringBuilder("#");
for(char c : s.toCharArray()){
newSB.append(c).append('#');
}
return newSB.toString();
}
回文子串（求個(gè)數(shù)）
動(dòng)態(tài)規(guī)劃
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for (int d = 0; d < n; d++) {
for (int L = 0; L < n - d; L++) {
if (d == 0) {
dp[L][L] = true;
count++;
continue;
}
if (d == 1) {
dp[L][L + 1] = s.charAt(L) == s.charAt(L + 1);
count += dp[L][L + 1] ? 1 : 0;
continue;
}
int R = L + d;
dp[L][R] = dp[L + 1][R - 1] & s.charAt(L) == s.charAt(R);
count += dp[L][R] ? 1 : 0;
}
}
return count;
}
馬拉車算法（Malacher算法壕探，中心擴(kuò)散算法的改進(jìn)版）
public int countSubstrings(String s) {
if (s.length() <= 1) {
return 1;
}
int count = 0;
String newString = preProcess(s); // 得到預(yù)處理字符串
int newLen = newString.length();
int[] armLen = new int[newLen]; // 記錄已經(jīng)計(jì)算過的回文子串半徑長度信息
int maxRight = 0; // 它是遍歷過的 i 的 i + armLen[i] 的最大者
int maxCenter = 0; // 它是遍歷過的 i 的 i + armLen[i] 的最大者 對(duì)應(yīng)的 i
for (int i = 0; i < newLen; i++) {
int offset = 0;
if (i < maxRight) {
int mirror = 2 * maxCenter - i;
offset = Math.min(maxRight - i, armLen[mirror]); // 馬拉車算法的關(guān)鍵, 即每次擴(kuò)散時(shí)不再從center開始, 而是從center +/- armLen開始
}
armLen[i] = expand(newString, i, offset); // 每次擴(kuò)散時(shí)不再從center開始, 而是從center +/- armLen開始
count += (armLen[i] + 1) / 2; // 記錄數(shù)量: +1是因?yàn)楸旧硪菜慊匚淖址? /2是因?yàn)樵黾拥淖址荒芩阍谠甲址?
// 更新maxRight以便最大限度利用已經(jīng)計(jì)算過的回文長度信息
if (i + armLen[i] > maxRight) {
maxRight = i + armLen[i];
maxCenter = i;
}
}
return count;
}
private int expand(String s, int center, int offSet) {
int len = s.length();
int i = center - (1 + offSet);
int j = center + (1 + offSet);
int armLen = offSet;
while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
i--;
j++;
armLen++;
}
return armLen;
}
private String preProcess(String s){
StringBuilder newSB = new StringBuilder("#");
for(char c : s.toCharArray()){
newSB.append(c).append('#');
}
return newSB.toString();
}
最長回文子序列
- 狀態(tài)
f[i][j] 表示 s 的第 i 個(gè)字符到第 j 個(gè)字符組成的子串中冈钦，最長的回文序列長度是多少。 - 轉(zhuǎn)移方程
如果 s 的第 i 個(gè)字符和第 j 個(gè)字符相同的話
如果 s 的第 i 個(gè)字符和第 j 個(gè)字符不同的話
- 遍歷變量（或者說遍歷順序）浩蓉，為了保證每個(gè)子問題一定是計(jì)算好的派继，我們將第一維變量設(shè)置為i和j的距離宾袜，這樣就能保證子問題一定是計(jì)算好的。
- 初始化
f[i][i] = 1 單個(gè)字符的最長回文序列是 1 - 結(jié)果
f[0][n - 1]
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int d = 0; d < n; d++) {
for (int left = 0; left < n - d; left++) {
if (d == 0) {
dp[left][left] = 1;
continue;
}
int right = left + d;
if (s.charAt(left) == s.charAt(right)) {
dp[left][right] = dp[left + 1][right - 1] + 2;
} else {
dp[left][right] = Math.max(dp[left + 1][right], dp[left][right - 1]);
}
}
}
return dp[0][n-1];
}
最長公共子序列
動(dòng)態(tài)規(guī)劃
最長公共子序列（Longest Common Subsequence驾窟，簡稱 LCS）是一道非常經(jīng)典的面試題目庆猫，因?yàn)樗慕夥ㄊ堑湫偷亩S動(dòng)態(tài)規(guī)劃，大部分比較困難的字符串問題都和這個(gè)問題一個(gè)套路绅络，比如說編輯距離月培。而且，這個(gè)算法稍加改造就可以用于解決其他問題恩急，所以說 LCS 算法是必須掌握的杉畜。
1）定義狀態(tài)變量dp[i][j]，表示字符串（0-i）和字符串（0-j）的LCS的長度衷恭，這里的i和j是各自字符串的最后一個(gè)字符下標(biāo)此叠。
2）確定狀態(tài)轉(zhuǎn)移方程：所謂確定狀態(tài)轉(zhuǎn)移方程，可以理解成求解dp[i][j]随珠，可以利用dp[<=i][<=j]的一切子問題的答案灭袁。
如果某個(gè)字符應(yīng)該在 LCS 中，那么這個(gè)字符肯定同時(shí)存在于 s1 和 s2 中窗看，因?yàn)長CS 是最長公共子序列茸歧。此時(shí)我們會(huì)聯(lián)想到比對(duì)s1.charAt[i] == s2.chatAt[j]。
如果s1.charAt[i] == s2.chatAt[j]的情況下显沈，dp[i][j]如何求软瞎？此時(shí)要利用dp[i][j]的定義，表示字符串（0-i）和字符串（0-j）的LCS的長度拉讯，此處i和j均為字符串的末尾涤浇，那么此字符必定在字符串（0-i）和字符串（0-j）的LCS中，所以有：dp[i][j] = dp[i-1][j-1] + 1遂唧；
如果s1.charAt[i] != s2.chatAt[j]的情況下芙代，dp[i][j]如何求？那么這兩個(gè)字符中至少有一個(gè)不在LCS中盖彭，所以有：dp[i][j] =Math.max(dp[i-1][j]纹烹，dp[i][j-1])；
3）邊界條件召边，字符串的下標(biāo)可以從1開始铺呵，這樣就避免的邊界條件的額外賦值。
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
兩個(gè)字符串的刪除操作
動(dòng)態(tài)規(guī)劃
此題同上面的最長子序列問題
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if (len1 == 0) {
return len2;
}
if (len2 == 0) {
return len1;
}
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return len1 + len2 - 2 * dp[len1][len2];
}
最長重復(fù)子數(shù)組
動(dòng)態(tài)規(guī)劃
public int findLength(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m == 0 || n == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1]; // dp[i][j]表示以A[i-1],B[j-1]為結(jié)尾元素的最長公共子數(shù)組長度
int maxComLen = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxComLen = Math.max(maxComLen, dp[i][j]);
}
}
}
return maxComLen;
}
空間優(yōu)化
- dp[i][j]只與dp[i-1][j-1]的值有關(guān)隧熙；所以可以降維片挂；
- 二維數(shù)組降成一維數(shù)組，一般將row變量取消；前提是row只與row-1狀態(tài)有關(guān)（最多row-2）音念；所以dp[i][j]降成dp[j]沪饺，則狀態(tài)方程變?yōu)閐p[j] = dp[j-1] + 1；
- 要保證dp[j-1]維持上一輪的值闷愤，這里有兩種方法可以實(shí)現(xiàn)：一般來說直接用一個(gè)變量保存上一輪的值即可整葡；另一種方法是內(nèi)循環(huán)倒序；
- 另外注意一點(diǎn)讥脐，上面的二維數(shù)組的賦零操作省略了遭居，因?yàn)槌跏蓟闹稻褪橇悖坏窃谝痪S數(shù)組中旬渠，賦零操作就是必要的俱萍，去改變上一輪的值。
public int findLength(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m == 0 || n == 0) {
return 0;
}
int[] dp = new int[n + 1];
int maxComLen = 0;
for (int i = 1; i <= m; i++) {
int prev = 0; // dp[i-1][j-1]
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (A[i - 1] == B[j - 1]) {
dp[j] = prev + 1;
}else {
dp[j] = 0;
}
maxComLen = Math.max(maxComLen, dp[j]);
prev = temp; // 保存上一輪的值
}
}
return maxComLen;
}
滑動(dòng)窗口
由于此題是連續(xù)子數(shù)組告丢，所以可用滑動(dòng)窗口解決枪蘑。
最長上升子序列(https://leetcode-cn.com/problems/longest-increasing-subsequence/)
給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度芋齿。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]腥寇，它的長度是 4。
說明:
可能會(huì)有多種最長上升子序列的組合觅捆，你只需要輸出對(duì)應(yīng)的長度即可。
你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 麻敌。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?
動(dòng)態(tài)規(guī)劃
定義 dp[i]為考慮前 i 個(gè)元素栅炒，以第 i個(gè)數(shù)字結(jié)尾的最長上升子序列的長度，注意nums[i] 必須被選取术羔。
我們從小到大計(jì)算 dp[]數(shù)組的值赢赊，在計(jì)算 dp[i]之前，我們已經(jīng)計(jì)算出dp[0…i?1] 的值级历，則狀態(tài)轉(zhuǎn)移方程為：
即考慮往 dp[0…i?1] 中最長的上升子序列后面再加一個(gè) nums[i]释移。由于 dp[j] 代表 nums[0…j] nums[j] 結(jié)尾的最長上升子序列，所以如果能從 dp[j]這個(gè)狀態(tài)轉(zhuǎn)移過來寥殖，那么 nums[i] 必然要大于nums[j]玩讳，才能將 nums[i] 放在 nums[j] 后面以形成更長的上升子序列。
最后嚼贡，整個(gè)數(shù)組的最長上升子序列即所有 dp[i] 中的最大值熏纯。
總結(jié)：最后的求解值，未必一定是dp數(shù)組中的某個(gè)值粤策，而是通過簡單的遍歷可以從dp數(shù)組中獲取到樟澜。
public static int lengthOfLIS(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int[] dp = new int[nums.length];
// 初始化
dp[0] = 1;
// 規(guī)劃
for (int tail = 1; tail < nums.length; tail++) {
int max = 0;
for (int i = 0; i < tail; i++) {
if (nums[tail] > nums[i]) {
max = Math.max(max, dp[i]);
}
}
dp[tail] = max + 1;
}
// 輸出dp數(shù)組中最大的即可
int max = 1;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, dp[i]);
}
return max;
}
貪心+二分法
對(duì)于此題的進(jìn)階，一旦出現(xiàn)logn的時(shí)間復(fù)雜度，往往可以聯(lián)想到二分法秩贰。
考慮一個(gè)簡單的貪心霹俺，如果我們要使上升子序列盡可能的長，則我們需要讓序列上升得盡可能慢毒费，因此我們希望每次在上升子序列最后加上的那個(gè)數(shù)盡可能的小吭服。
基于上面的貪心思路，我們維護(hù)一個(gè)數(shù)組 d[i]蝗罗，表示長度為 i 的最長上升子序列的末尾元素的最小值（已知元素）艇棕，用 len 記錄目前最長上升子序列的長度，起始時(shí) len 為 1串塑，d[1]=nums[0]沼琉。
同時(shí)我們可以注意到 d[i]是關(guān)于 i 單調(diào)遞增的。
我們依次遍歷數(shù)組nums[] 中的每個(gè)元素桩匪，并更新數(shù)組 d[] 和 len 的值打瘪。如果nums[i]>d[len] 則更新 len=len+1，否則在d[1…len]中找滿足d[i?1]<nums[j]<d[i] 的下標(biāo) i傻昙，并更新 d[i]=nums[j]闺骚。
根據(jù) d 數(shù)組的單調(diào)性，我們可以使用二分查找尋找下標(biāo) i妆档，優(yōu)化時(shí)間復(fù)雜度僻爽。
public static int lengthOfLIS2(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int len = 1;
int[] minTail = new int[nums.length+1];
minTail[len] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (len < nums.length && nums[i] > minTail[len]) {
len += 1;
minTail[len] = nums[i];
} else {
int l = 1;
int r = len;
while (l <= r) {
int m = l + (r - l) / 2;
if (minTail[m] < nums[i]) {
l = m + 1;
} else {
r = m - 1;
}
}
minTail[l] = nums[i];
}
}
return len;
}
最長遞增子序列的個(gè)數(shù)
動(dòng)態(tài)規(guī)劃
- 本題在"求解最長遞增子序列的長度"的基礎(chǔ)上，多維持一個(gè)記錄最長子序列的個(gè)數(shù)的數(shù)組贾惦。
int[] dp = new int[nums.length]; // dp[i]表示以nums[i]結(jié)尾的最長子序列的長度
int[] count = new int[nums.length]; // count[i]表示以nums[i]結(jié)尾的最長子序列的個(gè)數(shù)
- 代碼如下
public int findNumberOfLIS(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int[] dp = new int[nums.length]; // dp[i]表示以nums[i]結(jié)尾的最長子序列的長度
int[] count = new int[nums.length]; // count[i]表示以nums[i]結(jié)尾的最長子序列的個(gè)數(shù)
// 初始化
dp[0] = 1;
count[0] = 1;
// 規(guī)劃
for (int tail = 1; tail < nums.length; tail++) {
int max = 0;
int cnt = 1;
for (int i = 0; i < tail; i++) {
if (nums[tail] > nums[i]) {
if(dp[i] > max){
max = dp[i];
cnt = count[i];
}else if(dp[i] == max){
cnt += count[i];
}
}
}
dp[tail] = max + 1;
count[tail] = cnt;
}
// dp數(shù)組的最大者為最長子序列的長度
int maxLen = 1;
for (int i = 0; i < nums.length; i++) {
maxLen = Math.max(maxLen, dp[i]);
}
// 遍歷count數(shù)組
int countOfLIS = 0;
for(int i = 0; i < nums.length; i++){
if(dp[i] == maxLen){
countOfLIS += count[i];
}
}
return countOfLIS;
}
最小路徑和(https://leetcode-cn.com/problems/minimum-path-sum/)
給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格胸梆，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小须板。
說明：每次只能向下或者向右移動(dòng)一步碰镜。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。
二維動(dòng)態(tài)規(guī)劃
復(fù)雜度分析
時(shí)間復(fù)雜度 ：O(mn)习瑰。遍歷整個(gè)矩陣恰好一次绪颖。
空間復(fù)雜度 ：O(mn)。使用額外的一個(gè)同大小矩陣甜奄。O(1)柠横，直接使用原始的grid矩陣即可
public static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] minPath = new int[m][n];
// 初始化
minPath[0][0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i > 0 && j > 0) {
minPath[i][j] = Math.min(minPath[i - 1][j], minPath[i][j - 1]) + grid[i][j];
} else if (i == 0 && j > 0) {
minPath[i][j] = minPath[i][j - 1] + grid[i][j];
} else if (j == 0 && i > 0) {
minPath[i][j] = minPath[i - 1][j] + grid[i][j];
}
}
}
return minPath[m - 1][n - 1];
}
public static int minPathSum2(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i > 0 && j > 0) {
grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
} else if (i == 0 && j > 0) {
grid[i][j] = grid[i][j - 1] + grid[i][j];
} else if (j == 0 && i > 0) {
grid[i][j] = grid[i - 1][j] + grid[i][j];
}
}
}
return grid[m - 1][n - 1];
}
一維動(dòng)態(tài)規(guī)劃
逐行計(jì)算，計(jì)算下一行時(shí)利用上一行的結(jié)果贺嫂，并覆蓋之滓鸠；
public static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] minPath = new int[n];
// 初始化
minPath[0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i > 0 && j > 0) {
minPath[j] = Math.min(minPath[j], minPath[j - 1]) + grid[i][j];
} else if (i == 0 && j > 0) {
minPath[j] = minPath[j - 1] + grid[i][j];
} else if (i > 0 && j == 0) {
minPath[j] = minPath[j] + grid[i][j];
}
}
}
return minPath[n - 1];
}
背包問題的動(dòng)態(tài)規(guī)劃解法--歸納與總結(jié)
背包問題的判定
背包問題具備的特征：給定一個(gè)target详瑞，target可以是數(shù)字也可以是字符串诀黍，再給定一個(gè)數(shù)組nums，nums中裝的可能是數(shù)字弟跑，也可能是字符串，問：能否使用nums中的元素做各種排列組合得到target悠抹。
常見背包問題
分為三類：
排列組合問題：
組合總和 Ⅳ(https://leetcode-cn.com/problems/combination-sum-iv/)（排列問題）
目標(biāo)和(https://leetcode-cn.com/problems/target-sum/)（排列問題）
零錢兌換 II(https://leetcode-cn.com/problems/coin-change-2/)（組合問題）
狀態(tài)轉(zhuǎn)移公式：dp[i] = dp[i-num]True珠月、False問題
單詞拆分(https://leetcode-cn.com/problems/word-break/)
分割等和子集(https://leetcode-cn.com/problems/partition-equal-subset-sum/)
狀態(tài)轉(zhuǎn)移公式：dp[i] = dp[i] or dp[i-num]最大最小問題
一和零(https://leetcode-cn.com/problems/ones-and-zeroes/)
零錢兌換(https://leetcode-cn.com/problems/coin-change/)
狀態(tài)轉(zhuǎn)移公式：max(dp[i], dp[i-num]+1) 或者 dp[i] = min(dp[i], dp[i-num]+1)
對(duì)于狀態(tài)轉(zhuǎn)移公式的說明：
這里的狀態(tài)轉(zhuǎn)移公式只給出一個(gè)規(guī)劃變量，即輸出變量target楔敌； 有些問題是一維規(guī)劃問題啤挎，使用這一個(gè)規(guī)劃變量即可；有些問題是二維規(guī)劃問題卵凑，還需要添加其他規(guī)劃變量庆聘，比如數(shù)組的范圍下標(biāo)（前多少個(gè)元素）。對(duì)于target這個(gè)規(guī)劃變量勺卢，其取值范圍值得關(guān)注伙判，比如負(fù)值是否有意義，該怎么處理黑忱；是否截止到所求值即可宴抚；
組合總和 Ⅳ(https://leetcode-cn.com/problems/combination-sum-iv/)
給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)甫煞。
示例:
nums = [1, 2, 3]
target = 4
所有可能的組合為（這里其實(shí)是排列問題）：
(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)埃跷？
動(dòng)態(tài)規(guī)劃
考慮到這里順序不同的序列被視作不同的組合（即組合問題蕊玷，這是和零錢兌換問題不同的地方），所以按照下面的方法進(jìn)行動(dòng)態(tài)規(guī)劃：
定義狀態(tài)dp[i]為總和為i的所有可能的組合數(shù)弥雹。那么將所有組合按照最后一個(gè)數(shù)字進(jìn)行分類，就可以得到狀態(tài)轉(zhuǎn)移方程了：
public static int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 初始化
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
目標(biāo)和(https://leetcode-cn.com/problems/target-sum/)
給定一個(gè)非負(fù)整數(shù)數(shù)組延届，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)剪勿，S。現(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ù)組的和不會(huì)超過1000项钮。
保證返回的最終結(jié)果能被32位整數(shù)存下。
二維動(dòng)態(tài)規(guī)劃
這道題也是一個(gè)常見的背包問題，我們可以用類似求解背包問題的方法來求出可能的方法數(shù)烁巫。
我們用 dp[i][j] 表示用數(shù)組中的前 i 個(gè)元素署隘，組成和為 j 的方案數(shù)⊙窍叮考慮第 i 個(gè)數(shù) nums[i]磁餐，它可以被添加 + 或 -，因此狀態(tài)轉(zhuǎn)移方程如下：
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
這里j為和阿弃，所以j的取值范圍為-sum~sum诊霹，而由于數(shù)組下標(biāo)不能為負(fù)，所以對(duì)j可以進(jìn)行位移（用j+sum代替j）渣淳，于是狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)變?yōu)椋?br> dp[i][j+sum] = dp[i - 1][j + sum - nums[i]] + dp[i - 1][j + sum + nums[i]]
public static int findTargetSumWays(int[] nums, int S) {
// 目標(biāo)數(shù)的取值范圍: -sum ~ sum
int sum = 0;
for (int num : nums) {
sum += num;
}
// 考慮數(shù)組下標(biāo)不能小于0, 將每個(gè)目標(biāo)數(shù)加sum, 于是目標(biāo)數(shù)的取值范圍 0 ~ 2*sum
int n = nums.length;
int t = 2 * sum + 1;
int[][] dp = new int[n][t];
// 初始化(需要考慮0的情形)
if(nums[0] != 0){
dp[0][-nums[0] + sum] = 1;
dp[0][nums[0] + sum] = 1;
}else {
dp[0][sum] = 2;
}
for (int i = 1; i < n; i++) {
for (int j = -sum; j <= sum; j++) {
if (j + sum - nums[i] >= 0) {
dp[i][j + sum] += dp[i - 1][j + sum - nums[i]];
}
if (j + sum + nums[i] < t) {
dp[i][j + sum] += dp[i - 1][j + sum + nums[i]];
}
}
}
return S > sum ? 0 : dp[n - 1][S + sum];
}
零錢兌換 II(https://leetcode-cn.com/problems/coin-change-2/)
給定不同面額的硬幣和一個(gè)總金額脾还。寫出函數(shù)來計(jì)算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無限個(gè)水由。
示例 1:
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
輸入: amount = 3, coins = [2]
輸出: 0
解釋: 只用面額2的硬幣不能湊成總金額3荠呐。
示例 3:
輸入: amount = 10, coins = [10]
輸出: 1
注意:
你可以假設(shè)：
0 <= amount (總金額) <= 5000
1 <= coin (硬幣面額) <= 5000
硬幣種類不超過 500 種
結(jié)果符合 32 位符號(hào)整數(shù)
動(dòng)態(tài)規(guī)劃
二維的動(dòng)態(tài)規(guī)劃如下：
public static int change(int amount, int[] coins) {
if (coins.length == 0) {
return amount == 0 ? 1 : 0;
}
int[][] dp = new int[coins.length][amount + 1];
// 邊界條件
for (int j = 0; j <= amount; j++) {
dp[0][j] = j % coins[0] == 0 ? 1 : 0;
}
for (int i = 1; i < coins.length; i++) {
for (int j = 0; j <= amount; j++) {
if (j - coins[i] >= 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[coins.length - 1][amount];
}
空間優(yōu)化之后如下：
public static int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
// 初始化
dp[0] = 1;
// 動(dòng)態(tài)規(guī)劃
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
另一種二維的動(dòng)態(tài)規(guī)劃如下（空間優(yōu)化之后不通過）:
public static int change(int amount, int[] coins) {
if (coins.length == 0) {
return amount == 0 ? 1 : 0;
}
int[][] dp = new int[amount + 1][coins.length];
// 邊界條件
for (int j = 0; j < coins.length; j++) {
dp[0][j] = 1;
}
for (int i = 0; i <= amount; i++) {
dp[i][0] = i % coins[0] == 0 ? 1 : 0;
}
for (int i = 1; i <= amount; i++) {
for (int j = 1; j < coins.length; j++) {
if (i - coins[j] >= 0) {
dp[i][j] = dp[i][j - 1] + dp[i - coins[j]][j];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[amount][coins.length - 1];
}
單詞拆分(https://leetcode-cn.com/problems/word-break/)
給定一個(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
動(dòng)態(tài)規(guī)劃
這個(gè)方法的想法是對(duì)于給定的字符串（s）可以被拆分成子問題 s1 和 s2 彤恶。如果這些子問題都可以獨(dú)立地被拆分成符合要求的子問題钞钙，那么整個(gè)問題 s 也可以滿足。也就是，如果 "catsanddog" 可以拆分成兩個(gè)子字符串 "catsand" 和 "dog" 。子問題 "catsand" 可以進(jìn)一步拆分成 "cats" 和 "and" ，這兩個(gè)獨(dú)立的部分都是字典的一部分，所以 "catsand" 滿足題意條件，再往前冻璃， "catsand" 和 "dog" 也分別滿足條件遏插，所以整個(gè)字符串 "catsanddog" 也滿足條件上岗。
public static boolean wordBreak3(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int end = 1; end <= s.length(); end++){
for(int start = 0; start < end; start++){
if(dp[start] && wordDict.contains(s.substring(start, end))){
dp[end] = true;
break;
}
}
}
return dp[s.length()];
}
分割等和子集(https://leetcode-cn.com/problems/partition-equal-subset-sum/)
給定一個(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è)元素和相等的子集.
動(dòng)態(tài)規(guī)劃
做這道題需要做這樣一個(gè)等價(jià)轉(zhuǎn)換：是否可以從這個(gè)數(shù)組中挑選出一些正整數(shù)，使得這些數(shù)的和等于整個(gè)數(shù)組元素的和的一半前域。
即將此問題轉(zhuǎn)化為0-1背包問題：背包容量為sum/2 辕近，物品為題意給出的數(shù)組 ，問能否取出一次物品恰好裝滿背包 匿垄。
public static boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
boolean[][] dp = new boolean[nums.length][target + 1];
// 邊界計(jì)算
for (int i = 0; i < nums.length; i++) {
dp[i][0] = true;
}
for (int j = 1; j <= target; j++) {
dp[0][j] = nums[0] == j;
}
for (int i = 1; i < nums.length; i++) {
for (int j = 1; j <= target; j++) {
if (j - nums[i] >= 0) {
dp[i][j] = dp[i - 1][j - nums[i]] | dp[i - 1][j];
}
}
if (dp[i][target] == true) {
return true;
}
}
return false;
}
一和零(https://leetcode-cn.com/problems/ones-and-zeroes/)
在計(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" 芯砸。
思路：把總共的 0 個(gè) 1 的個(gè)數(shù)視為背包的容量，每一個(gè)字符串視為裝進(jìn)背包的物品给梅。這道題就可以使用 0-1 背包問題的思路完成假丧。這里的目標(biāo)值是能放進(jìn)背包的字符串的數(shù)量。
第 1 步：定義狀態(tài)
依然是嘗試「題目問啥动羽，就把啥定義成狀態(tài)」包帚。
dp[k][i][j] 表示輸入字符串在 能夠使用 i 個(gè) 0 和 j 個(gè) 1 的情況下，能夠容納前k個(gè)字符串的最大數(shù)量运吓。
第 2 步：狀態(tài)轉(zhuǎn)移方程
dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - c0][j - c1] + 1)
c0:當(dāng)前字符串（即第k個(gè)字符串）使用0的個(gè)數(shù);
c1:當(dāng)前字符串（即第k個(gè)字符串）使用1的個(gè)數(shù)渴邦；
第 3 步：初始化
為了避免分類討論疯趟，通常多設(shè)置一行。這里可以認(rèn)為谋梭，第 0 個(gè)字符串是空串信峻。第 0 行默認(rèn)初始化為 0。
若不增加空串瓮床，則需要單獨(dú)為k=0的情況賦值盹舞；
第 4 步：輸出
輸出是最后一個(gè)狀態(tài)，即：dp[len][m][n]纤垂。
// 增加空串避免初始化賦值
public static int findMaxForm(String[] strs, int m, int n) {
int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
// 動(dòng)態(tài)規(guī)劃
for (int k = 1; k <= strs.length; k++) {
int[] res = find(strs[k - 1]);
int c0 = res[0];
int c1 = res[1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i >= c0 && j >= c1) {
dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - c0][j - c1] + 1);
} else {
dp[k][i][j] = dp[k - 1][i][j];
}
}
}
}
return dp[strs.length][m][n];
}
public static int[] find(String s) {
int[] c = new int[2];
for (int i = 0; i < s.length(); i++) {
c[s.charAt(i)-'0']++;
}
return c;
}
考慮空間優(yōu)化：
因?yàn)楫?dāng)前行只參考了上一行的值矾策，因此可以使用「滾動(dòng)數(shù)組」或者「從后向前賦值」的方法優(yōu)化空間。這里采用「從后向前賦值」的方法峭沦。
1）優(yōu)化空間只是將dp降維贾虽，實(shí)際的for循環(huán)仍然是三層；
2）dp降維后為什么里循環(huán)要從后向前賦值：為了使得上一次循環(huán)的結(jié)果不被下一次循環(huán)的結(jié)果覆蓋掉吼鱼，需要從后向前賦值蓬豁。
舉例說明：假設(shè)d[3][3] = d[1][1] + 1，實(shí)際想要得到的效果是當(dāng)前循環(huán)的d[3][3]應(yīng)該利用到上一次循環(huán)的d[1][1]結(jié)果菇肃；如果i和j從小到大賦值地粪，會(huì)先將d[1][1]的值覆蓋住，導(dǎo)致上一輪的結(jié)果還沒有被利用到就已經(jīng)沒了琐谤。
public static int findMaxForm3(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
// 動(dòng)態(tài)規(guī)劃
for (String str : strs) {
int[] res = find(str);
int c0 = res[0];
int c1 = res[1];
for (int i = m; i >=0; i--) {
for (int j = n; j >= 0; j--) {
if (i >= c0 && j >= c1) {
dp[i][j] = Math.max(dp[i][j], dp[i - c0][j - c1] + 1);
}
}
}
}
return dp[m][n];
}
零錢兌換(https://leetcode-cn.com/problems/coin-change/)
給定不同面額的硬幣 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ù)量是無限的。
動(dòng)態(tài)規(guī)劃解法
1）首先按照套路织阳，題目問什么眶蕉，就把什么當(dāng)做狀態(tài)變量
2）本題有兩個(gè)狀態(tài)變量，一個(gè)是coins索引唧躲，一個(gè)是總金額amount造挽；不妨進(jìn)行二維動(dòng)態(tài)規(guī)劃，但是哪一個(gè)變量放在外循環(huán)弄痹，哪一個(gè)變量放在內(nèi)循環(huán)饭入，是需要重點(diǎn)解決的問題：
如果把coins的索引放在外層，總金額放在內(nèi)層肛真，那么求解當(dāng)前問題dp[coin][amount]時(shí)圣拄，并不能利用任何dp[*][amount-1]子問題的解；
如果把總金額放在外層毁欣，把coins的索引放在內(nèi)層庇谆，那么求解當(dāng)前問題dp[amount][coin_ind]，可以利用dp[amount][coin_ind-1]這一子問題的解：
dp[amount][coin_ind] = min(dp[amount][coin_ind-1], dp[amount-coin_val][coin_ind]+1);
3)考慮到本題求解的是最小值凭疮，所以初始化時(shí)饭耳，不能默認(rèn)初始化為0，需要設(shè)置為無窮大执解，或者已知的不可能達(dá)到的大值寞肖。
public static int coinChange(int[] coins, int amount) {
int MAX = amount + 1;
int[][] dp = new int[amount + 1][coins.length];
// 初始化
for (int i = 0; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i == 0) {
dp[i][j] = 0;
} else if (j == 0 && i % coins[j] == 0) {
dp[i][j] = i / coins[j];
} else {
dp[i][j] = MAX;
}
}
}
for (int i = 1; i <= amount; i++) {
for (int j = 1; j < coins.length; j++) {
if (i - coins[j] >= 0) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - coins[j]][j] + 1);
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[amount][coins.length - 1] == MAX ? -1 : dp[amount][coins.length - 1];
}
空間優(yōu)化
觀察狀態(tài)轉(zhuǎn)移語句：
dp[i][j] = Math.min(dp[i][j - 1], dp[i - coins[j]][j] + 1);
dp[*][j] 的值只可能依賴于dp[*][j - 1]或者dp[*][j] 的值，所以可以去掉[j]衰腌。同時(shí)新蟆，初始條件也會(huì)簡化。
public static int coinChange(int[] coins, int amount) {
int MAX = amount + 1;
int[] dp = new int[amount + 1];
// 初始化
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = MAX;
}
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == MAX ? -1 : dp[amount];
}
不同路徑(https://leetcode-cn.com/problems/unique-paths/)
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）右蕊。
機(jī)器人每次只能向下或者向右移動(dòng)一步琼稻。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑饶囚？
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始帕翻，總共有 3 條路徑可以到達(dá)右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
提示：
1 <= m, n <= 100
題目數(shù)據(jù)保證答案小于等于 2 * 10 ^ 9
二維動(dòng)態(tài)規(guī)劃
到達(dá)[i,j]的路徑只可能有兩類情況：從[i-1,j]往下走或者從[i.j-1]往右走萝风；
public static int uniquePath(int m, int n) {
int[][] dp = new int[m][n];
//邊界條件
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
不同路徑 II
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
continue;
}
if (i == 0 && j == 0) {
dp[i][j] = 1;
continue;
}
if (i == 0) {
dp[i][j] = dp[i][j - 1];
continue;
}
if (j == 0) {
dp[i][j] = dp[i - 1][j];
continue;
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
- 空間優(yōu)化
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (i == 0 && j == 0) {
dp[j] = 1;
continue;
}
if (i == 0) {
dp[j] = dp[j - 1];
continue;
}
if (j == 0) {
continue;
}
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
打家劫舍(https://leetcode-cn.com/problems/house-robber/)
你是一個(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)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額堕花。
示例 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 壕曼。
動(dòng)態(tài)規(guī)劃
對(duì)于每個(gè)新加入的元素nums[k]苏研，求sum只有兩種情況：加入nums[k]和不加入nums[k]；
1）加入nums[k]腮郊，那么dp[k] = dp[k-2] + nums[k];
雖然dp[k-1]摹蘑，也有可能沒有將nums[k-1]納入求和，但這種情況下dp[k-1]=dp[k-2]轧飞，所以上式也成立衅鹿。
2）不加入nums[k]撒踪，那么dp[k] = dp[k-1]；
取兩者之大即可大渤；
public static int rob(int[] nums) {
int n = nums.length;
if(n == 0){
return 0;
}
int[] dp = new int[n];
// 初始化
dp[0] = nums[0];
if(n == 1){
return dp[0];
}
dp[1] = Math.max(nums[0], nums[1]);
for (int k = 2; k < n; k++) {
dp[k] = Math.max(dp[k - 1], dp[k - 2] + nums[k]);
}
return dp[n - 1];
}
打家劫舍 II(https://leetcode-cn.com/problems/house-robber-ii/)
你是一個(gè)專業(yè)的小偷制妄，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金泵三。這個(gè)地方所有的房屋都圍成一圈耕捞，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)烫幕，相鄰的房屋裝有相互連通的防盜系統(tǒng)俺抽，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警较曼。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組磷斧，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額诗芜。
示例 1:
輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 號(hào)房屋（金額 = 2）瞳抓，然后偷竊 3 號(hào)房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?br>
示例 2:
輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 號(hào)房屋（金額 = 1），然后偷竊 3 號(hào)房屋（金額 = 3）伏恐。
偷竊到的最高金額 = 1 + 3 = 4 孩哑。
動(dòng)態(tài)規(guī)劃
環(huán)狀排列意味著第一個(gè)房子和最后一個(gè)房子中只能選擇一個(gè)偷竊，因此可以把此環(huán)狀排列房間問題約化為兩個(gè)單排排列房間子問題：
在不偷竊第一個(gè)房子的情況下（即 nums[1:n]）翠桦，最大金額是 p1横蜒；
在不偷竊最后一個(gè)房子的情況下（即 nums[0:n-1]），最大金額是 p2销凑。
綜合偷竊最大金額： 為以上兩種情況的較大值丛晌，即 max(p1,p2) 。
public static int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int n = nums.length;
return Math.max(rob_single(nums, 0, n - 2), rob_single(nums, 1, n - 1));
}
public static int rob_single(int[] nums, int start, int end) {
int n = end - start + 1;
int[] dp = new int[n];
// 初始化
dp[0] = nums[start];
if (n == 1) {
return dp[0];
}
dp[1] = Math.max(nums[start], nums[start + 1]);
for (int k = 2; k < n; k++) {
dp[k] = Math.max(dp[k - 1], dp[k - 2] + nums[start + k]);
}
return dp[n - 1];
}
最大正方形
動(dòng)態(tài)規(guī)劃
注意：之前的一系列背包問題的動(dòng)態(tài)規(guī)劃思路是：問題問什么斗幼，我們就把什么定義為規(guī)劃的狀態(tài)變量澎蛛；但是，如果不是背包問題蜕窿，那么這個(gè)規(guī)律不再適用谋逻！往往要結(jié)合問題的特征進(jìn)行某些條件的附加，很多情況下的dp數(shù)組不會(huì)直觀給出哪個(gè)元素是問題的答案桐经，而是需要遍歷dp數(shù)組毁兆，得到解決問題的某個(gè)關(guān)鍵值（一般為最大/最小值）。
以此題為例進(jìn)行說明：
第一步：如果直接把dp[i][j]定義為問題的所問：(0,0)~(i,j)的二維矩陣內(nèi)阴挣，只包含1的最大正方形的面積/邊長气堕，你會(huì)發(fā)現(xiàn)，完全無法利用起相鄰子問題的解，困難之處在于0的存在茎芭，會(huì)將連續(xù)為1的正方形切割開來揖膜。
第二步：既然不能直接將問題所問定義為狀態(tài)變量，我們考慮添加附加條件：dp[i][j]定義為以(i,j)為右下角的骗爆，只包含1的最大正方形的邊長次氨。添加了附加條件之后，我們解決了上面的困難摘投，即對(duì)于0的存在，對(duì)應(yīng)的dp[i][j]值為零虹蓄，因?yàn)橐?為右下角則不可能只包含1犀呼，所以邊長必定為0。那么在這種情況下薇组，我們計(jì)算得到的dp數(shù)組外臂，如何求得最后的答案：即dp[i][j]數(shù)組中最大邊長的平方。
第三步：在確定dp[i][j]的定義后律胀，我們需要計(jì)算整個(gè)dp[i][j]數(shù)組宋光。
A）(i,j)為0，dp[i][j]則為零炭菌。
B）(i,j)為1：
1）若(i-1,j-1)罪佳，(i,j-1)，(i-1,j)任意一個(gè)為0黑低，此時(shí)dp[i][j]為1赘艳；
2）若(i-1,j-1)，(i,j-1)克握，(i-1,j)全為1蕾管，且對(duì)應(yīng)的dp[i-1][j-1]，dp[i][j-1]菩暗，dp[i-1][j]分別對(duì)應(yīng)為n掰曾，p，q停团，如下圖所示旷坦，則此時(shí)dp[i][j]為min(n,p,q)+1;
然后發(fā)現(xiàn)2）的遞推公式也包含了1）的情況贮预；
代碼如下：
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if (m == 0) {
return 0;
}
int n = matrix[0].length;
if (n == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
int maxEdge = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
maxEdge = Math.max(maxEdge, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxEdge * maxEdge;
}
統(tǒng)計(jì)全為 1 的正方形子矩陣
動(dòng)態(tài)規(guī)劃
此題與上面求最大正方形面積的題幾乎一致包归。
規(guī)劃的狀態(tài)變量完全一樣：dp[i][j] 表示以(i,j)為右下角的坷襟，只包含1的最大正方形的邊長秃诵；這個(gè)最大邊長同時(shí)表示以(i,j)為右下角的正方形的個(gè)數(shù)：假設(shè)最大正方形的邊長為3轨功，那么以此點(diǎn)為右下角的正方形有邊長為3丰辣，邊長為2乍恐，邊長為1的正方形各一個(gè)默蚌，總共3個(gè)。于是此題最后的總數(shù)即dp[i][j]的所有元素求和漱办。
計(jì)算dp[i][j]數(shù)組的狀態(tài)轉(zhuǎn)移公式跟上面求最大正方形面積的完全一致：
A）(i,j)為0这刷，dp[i][j]則為零。
B）(i,j)為1：dp[i][j]為min(dp[i-1][j-1]娩井，dp[i][j-1]暇屋，dp[i-1][j]) + 1;
代碼如下：
public int countSquares(int[][] matrix) {
int m = matrix.length;
if (m == 0) {
return 0;
}
int n = matrix[0].length;
if (n == 0) {
return 0;
}
int totalCount = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == 1) {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
totalCount += dp[i][j];
} else {
dp[i][j] = 0;
}
}
}
return totalCount;
}
解碼方法
動(dòng)態(tài)規(guī)劃
1）狀態(tài)轉(zhuǎn)移方程：dp[i]表示0~i的字符串的解碼總數(shù)。第i個(gè)字符可以自己單獨(dú)解碼洞辣，也可以和前一個(gè)字符一起解碼（滿足一定條件）咐刨。所以狀態(tài)轉(zhuǎn)移方程為：dp[i] = dp[i-1]或者dp[i] = dp[i-1] + dp[i-2]。
2）注意'0'的存在扬霜，'0'不能作為開頭定鸟；
public int numDecodings(String s) {
int n = s.length();
if (n == 0 || s.charAt(0) == '0') {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i < n; i++) {
if (s.charAt(i) != '0') {
if (s.charAt(i - 1) != '0' && s.substring(i - 1, i + 1).compareTo("26") <= 0) {
dp[i] = dp[i - 1] + (i > 1 ? dp[i - 2] : 1);
} else {
dp[i] = dp[i - 1];
}
} else if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
dp[i] = (i > 1 ? dp[i - 2] : 1);
} else {
return 0;
}
}
return dp[n - 1];
}
乘積最大子數(shù)組
動(dòng)態(tài)規(guī)劃
1）若不存在負(fù)數(shù)，只存在0和正數(shù)：令dp[i]表示以nums[i]結(jié)尾的最大子數(shù)組乘積著瓶，則 dp[i] = max(dp[i-1] * nums[i], nums[i])联予。
2）由于存在負(fù)數(shù)，那么會(huì)導(dǎo)致最大的變最小的材原，最小的變最大的沸久。因此還需要維護(hù)當(dāng)前最小值的dp數(shù)組。
3）則有：令dp_max[i]表示以nums[i]結(jié)尾的最大子數(shù)組乘積余蟹，令dp_min[i]表示以nums[i]結(jié)尾的最小子數(shù)組乘積卷胯，于是則有了下面的狀態(tài)轉(zhuǎn)移方程：
dp_max[i] = Math.max(nums[i], Math.max(nums[i] * dp_max[i-1], nums[i] * dp_min[i-1]));
dp_min[i] = Math.min(nums[i], Math.min(nums[i] * dp_max[i-1], nums[i] * dp_min[i-1]));
4）最后取出dp_max數(shù)組中最大的值即可；
代碼如下：
public static int maxProduct(int[] nums) {
int n = nums.length;
if(n == 1){
return nums[0];
}
int ans = nums[0];
int[] dp_max = new int[n];
int[] dp_min = new int[n];
dp_max[0] = nums[0];
dp_min[0] = nums[0];
for(int i=1; i<n; i++){
int num1 = nums[i] * dp_max[i-1];
int num2 = nums[i] * dp_min[i-1];
dp_max[i] = Math.max(nums[i], Math.max(num1, num2));
dp_min[i] = Math.min(nums[i], Math.min(num1, num2));
ans = Math.max(ans, dp_max[i]);
}
return ans;
}
不同的二叉搜索樹
動(dòng)態(tài)規(guī)劃
public int numTrees(int n) {
int[] total = new int[n + 1];
total[0] = 1;
total[1] = 1;
for (int i = 2; i <= n; i++) {
total[i] = 0;
for(int root = 1; root <= i; root++){
total[i] += total[root - 1] * total[i - root];
}
}
return total[n];
}
股票系列問題總結(jié)
狀態(tài)變量：
dp[i][k][0/1]
i: 天數(shù); 取值:0~n-1, n為給出的股票價(jià)格的天數(shù)
k: 最大允許交易次數(shù); 取值:k~1, 從大到小, 因?yàn)槭亲畲笤试S交易次數(shù), 而不是交易次數(shù)
0/1: 是否持有股票; 0表示沒有持有股票; 1表示持有股票;
比如說 dp[3][2][1] 的含義就是：今天是第三天客叉，我現(xiàn)在手上持有著股票诵竭，至今最多進(jìn)行 2 次交易。
再比如 dp[2][3][0] 的含義：今天是第二天兼搏，我現(xiàn)在手上沒有持有股票卵慰，至今最多進(jìn)行 3 次交易。
狀態(tài)轉(zhuǎn)移公式：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 選擇 rest , 選擇 sell )
解釋：今天我沒有持有股票佛呻，有兩種可能：
要么是我昨天就沒有持有裳朋，然后今天選擇 rest，所以我今天還是沒有持有吓著；
要么是我昨天持有股票鲤嫡，但是今天我 sell 了，所以我今天沒有持有股票了绑莺。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 選擇 rest , 選擇 buy )
解釋：今天我持有著股票暖眼，有兩種可能：
要么我昨天就持有著股票，然后今天選擇 rest纺裁，所以我今天還持有著股票诫肠；
要么我昨天本沒有持有司澎，但今天我選擇 buy，所以今天我就持有股票了栋豫。
邊界條件：
dp[0][k][0] = 0
解釋：第0天挤安，未持有股票，這時(shí)候的利潤當(dāng)然是 0 丧鸯。
dp[0][k][1] = -price[0]
解釋：第0天蛤铜，持有股票，此時(shí)反而付出price[0]的價(jià)格購買股票 丛肢。
dp[i][0][0] = 0
解釋： k = 0 意味著根本不允許交易围肥，這時(shí)候利潤當(dāng)然是 0 。
dp[i][0][1] = -infinity
解釋：不允許交易的情況下蜂怎，是不可能持有股票的虐先，用負(fù)無窮表示這種不可能。
不同的股票問題派敷，根據(jù)條件的不同，可以進(jìn)行降維撰洗。
買賣股票的最佳時(shí)機(jī)
動(dòng)態(tài)規(guī)劃
根據(jù)通用的狀態(tài)轉(zhuǎn)移公式：(當(dāng)然此題用貪婪解法篮愉，一次遍歷即可解決)
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
由于本題k=1，即最多允許一次交易差导，所以上面的狀態(tài)轉(zhuǎn)移公式中的dp[i-1][k-1][0]此項(xiàng)為0试躏。從而上面的狀態(tài)轉(zhuǎn)移公式中的k這一狀態(tài)變量可以移除。
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], - prices[i])
代碼如下设褐，從上面的狀態(tài)轉(zhuǎn)移公式中可以看出颠蕴，對(duì)于狀態(tài)變量i，只會(huì)跟i-1有關(guān)助析，所以可以進(jìn)一步進(jìn)行空間優(yōu)化犀被。但是空間優(yōu)化之后的代碼，直觀上比較難以理解外冀。
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][] dp = new int[prices.length][2];
for (int i = 0; i < prices.length; i++) {
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = -prices[0];
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[prices.length - 1][0];
}
// 空間優(yōu)化
public int maxProfit_savespace(int[] prices) {
if (prices.length == 0) {
return 0;
}
int dp_0 = 0;
int dp_1 = -prices[0];
for (int i = 1; i < prices.length; i++) {
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp_0 = Math.max(dp_0, dp_1 + prices[i]);
// dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp_1 = Math.max(dp_1, -prices[i]);
}
// return dp[prices.length-1][0];
return dp_0;
}
買賣股票的最佳時(shí)機(jī) II
動(dòng)態(tài)規(guī)劃
根據(jù)通用的狀態(tài)轉(zhuǎn)移公式：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
由于本題k=無窮寡键，即允許無限次交易，所以上面的狀態(tài)轉(zhuǎn)移公式中的k或者k-1都等于無窮大雪隧，于是可以移除此變量西轩。
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
代碼如下，從上面的狀態(tài)轉(zhuǎn)移公式中可以看出脑沿，對(duì)于狀態(tài)變量i藕畔，只會(huì)跟i-1有關(guān)，所以可以進(jìn)一步進(jìn)行空間優(yōu)化庄拇。但是空間優(yōu)化之后的代碼注服，直觀上比較難以理解。
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][] dp = new int[prices.length][2];
for (int i = 0; i < prices.length; i++) {
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = -prices[0];
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.length - 1][0];
}
// 空間優(yōu)化
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int dp_0 = 0;
int dp_1 = -prices[0];
for (int i = 1; i < prices.length; i++) {
int temp = dp_0;
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp_0 = Math.max(dp_0, dp_1 + prices[i]);
// dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp_1 = Math.max(dp_1, temp - prices[i]);
}
// return dp[prices.length-1][0];
return dp_0;
}
最佳買賣股票時(shí)機(jī)含冷凍期
動(dòng)態(tài)規(guī)劃
本題與股票問題||類似，都允許無限次交易祠汇。不同的是交易冷凍期為1天仍秤，所以狀態(tài)轉(zhuǎn)移方程如下：唯一的不同是買入的時(shí)候，要從i-2的狀態(tài)轉(zhuǎn)移可很，而不是i-1诗力。
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解釋：第 i 天選擇 buy 的時(shí)候，要從 i-2 的狀態(tài)轉(zhuǎn)移我抠，而不是 i-1 苇本。
代碼：
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][] dp = new int[prices.length][2];
for (int i = 0; i < prices.length; i++) {
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = -prices[0];
continue;
}
if (i == 1) {
dp[1][0] = Math.max(0, -prices[0] + prices[1]);
dp[1][1] = Math.max(-prices[0], -prices[1]);
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
}
return dp[prices.length - 1][0];
}
// 空間優(yōu)化
public int maxProfit(int[] prices) {
if (prices.length <= 1) {
return 0;
}
// 初始化:第1天的值;
// 另外一種更加簡潔的初始化是賦值為第-1天的值，i從0開始遍歷：dp_0 = 0; dp_1 = Interger.MIN_VAL
int dp_0 = Math.max(0, -prices[0] + prices[1]);
int dp_1 = Math.max(-prices[0], -prices[1]);
int dp_pre_0 = 0; // dp_pre_0 用于保存dp[i - 2][0]的值
for (int i = 2; i < prices.length; i++) {
int temp = dp_0; //上一輪循環(huán)結(jié)束后dp_0的值
dp_0 = Math.max(dp_0, dp_1 + prices[i]); // 本輪循環(huán)結(jié)束后dp_0的值
dp_1 = Math.max(dp_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp; // 對(duì)于下一輪循環(huán)而言, dp_pre_0就是上上輪的dp_0的值了
}
return dp_0;
}
買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)
動(dòng)態(tài)規(guī)劃
本題與股票問題||類似菜拓，都允許無限次交易瓣窄。不同的是多了交易手續(xù)費(fèi)，所以狀態(tài)轉(zhuǎn)移方程如下：唯一的不同是買入的時(shí)候纳鼎，費(fèi)用還要額外減去手續(xù)費(fèi)俺夕。
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解釋：第 i 天選擇 buy 的時(shí)候，要額外減去手續(xù)費(fèi)用贱鄙。
代碼：
public int maxProfit(int[] prices, int fee) {
if (prices.length == 0) {
return 0;
}
int[][] dp = new int[prices.length][2];
for (int i = 0; i < prices.length; i++) {
if (i == 0) {
dp[0][0] = 0;
dp[0][1] = -prices[0] - fee;
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
}
return dp[prices.length - 1][0];
}
// 空間優(yōu)化
public int maxProfit(int[] prices, int fee) {
if (prices.length <= 1) {
return 0;
}
// 初始化:第0天的值（另外一種更簡化的初始化方法：初始化為第-1天的值劝贸，dp_0 = 0; dp_1 = Integer.MIN_VAL；i從0開始遍歷）
int dp_0 = 0;
int dp_1 = -prices[0] - fee;
for (int i = 1; i < prices.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1 + prices[i]);
dp_1 = Math.max(dp_1, temp - prices[i] - fee);
}
return dp_0;
}
買賣股票的最佳時(shí)機(jī) III
動(dòng)態(tài)規(guī)劃
根據(jù)通用的狀態(tài)轉(zhuǎn)移公式：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
此題中k=2逗宁，即最大允許交易次數(shù)為2映九，我們可以將最大允許買入次數(shù)設(shè)置為2（或者最大賣出次數(shù)設(shè)置為2）。由于最大允許交易次數(shù)是逐漸減小的瞎颗，所以for循環(huán)中件甥，k是從大到小遞減。由于k=2哼拔，k可取2和1（當(dāng)k取0時(shí)對(duì)應(yīng)的值為0）引有，所以可以將第二維、第三維變量列舉出來管挟，進(jìn)行空間規(guī)劃轿曙，共2*2=4個(gè)變量。
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int maxK = 2;
int[][][] dp = new int[prices.length][maxK + 1][2];
for (int i = 0; i < prices.length; i++) {
for (int k = maxK; k >= 1; k--) {
if (i == 0) {
dp[i][k][0] = 0;
dp[i][k][1] = -prices[0];
continue;
}
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][maxK][0];
}
// 空間優(yōu)化
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
// 初始化賦值, 即i=0時(shí)賦值
int dp_1_0 = 0;
int dp_1_1 = -prices[0];
int dp_2_0 = 0;
int dp_2_1 = -prices[0];
for (int i = 1; i < prices.length; i++) {
int temp = dp_1_0;
dp_1_0 = Math.max(dp_1_0, dp_1_1 + prices[i]);
dp_1_1 = Math.max(dp_1_1, - prices[i]);
dp_2_0 = Math.max(dp_2_0, dp_2_1 + prices[i]);
dp_2_1 = Math.max(dp_2_1, temp - prices[i]);
}
return dp_2_0;
}
買賣股票的最佳時(shí)機(jī) IV
動(dòng)態(tài)規(guī)劃
依舊根據(jù)通用的狀態(tài)轉(zhuǎn)移公式：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
此題中k值為變量僻孝，即最大允許交易次數(shù)為k导帝，我們可以將最大允許買入次數(shù)設(shè)置為k（或者最大賣出次數(shù)設(shè)置為k）。
此題和上題基本一致穿铆，但出現(xiàn)了內(nèi)存超出空間問題您单，原因是輸入的k值很大，其實(shí)當(dāng)k大于n/2時(shí)荞雏，就跟無窮大的效果是一致的虐秦，因?yàn)樽疃嘀豢赡芙灰譶/2次平酿。所以當(dāng)輸入的k大于n/2時(shí)，我們直接利用前面第二題的答案返回即可悦陋。
// 原始動(dòng)態(tài)規(guī)劃
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][][] dp = new int[prices.length][k + 1][2];
for (int i = 0; i < prices.length; i++) {
for (int t = k; t >= 1; t--) {
if (i == 0) {
dp[i][t][0] = 0;
dp[i][t][1] = -prices[0];
continue;
}
dp[i][t][0] = Math.max(dp[i - 1][t][0], dp[i - 1][t][1] + prices[i]);
dp[i][t][1] = Math.max(dp[i - 1][t][1], dp[i - 1][t - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][k][0];
}
// 空間優(yōu)化的答案
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
if(k > prices.length / 2){
return maxProfit_k_inf(prices);
}
int[][] dp_0 = new int[prices.length][k + 1];
int[][] dp_1 = new int[prices.length][k + 1];
for (int i = 0; i < prices.length; i++) {
for (int t = k; t >= 1; t--) {
if (i == 0) {
dp_0[i][t] = 0;
dp_1[i][t] = -prices[0];
continue;
}
dp_0[i][t] = Math.max(dp_0[i - 1][t], dp_1[i - 1][t] + prices[i]);
dp_1[i][t] = Math.max(dp_1[i - 1][t], dp_0[i - 1][t - 1] - prices[i]);
}
}
return dp_0[prices.length - 1][k];
}
// 代碼重用:即k為無窮時(shí)的答案
public int maxProfit_k_inf(int[] prices) {
if (prices.length == 0) {
return 0;
}
int dp_0 = 0;
int dp_1 = -prices[0];
for (int i = 1; i < prices.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1 + prices[i]);
dp_1 = Math.max(dp_1, temp - prices[i]);
}
return dp_0;
}
三角形最小路徑和
動(dòng)態(tài)規(guī)劃
public int minimumTotal(List<List<Integer>> triangle) {
int m = triangle.size();
if (m == 0) {
return 0;
}
int[][] dp = new int[m][m];
dp[0][0] = triangle.get(0).get(0);
for (int row = 1; row < m; row++) {
for (int col = 0; col <= row; col++) {
int num = triangle.get(row).get(col);
if (col == 0) { // 最左端
dp[row][col] = dp[row - 1][col] + num;
}else if(col == row){ // 最右端
dp[row][col] = dp[row - 1][col - 1] + num;
}else { // 中間
dp[row][col] = Math.min(dp[row - 1][col - 1] + num, dp[row - 1][col] + num);
}
}
}
// 從最后一行中找出最短路徑
int minPath = dp[m - 1][0];
for (int i = 1; i < m; i++) {
minPath = Math.min(minPath, dp[m - 1][i]);
}
return minPath;
}
空間優(yōu)化
記住空間優(yōu)化的技巧：
觀察自頂向下的代碼會(huì)發(fā)現(xiàn)蜈彼，對(duì)第row行的最小路徑和的推導(dǎo)，只需要第row-1行的dp[row - 1][col]和dp[row - 1][col - 1]元素即可俺驶⌒夷妫可以使用兩個(gè)變量暫存。
一維的dp數(shù)組只存儲(chǔ)第row行的最小路徑和暮现。
// 空間優(yōu)化
public int minimumTotal(List<List<Integer>> triangle) {
int m = triangle.size();
if (m == 0) {
return 0;
}
int[] dp = new int[m];
dp[0] = triangle.get(0).get(0);
int prev = 0; // 暫存dp[row - 1][col - 1]
int curr; // 暫存暫存dp[row - 1][col]
for (int row = 1; row < m; row++) {
for (int col = 0; col <= row; col++) {
int num = triangle.get(row).get(col);
curr = dp[col];
if (col == 0) { // 最左端
dp[col] = curr + num;
}else if(col == row){ // 最右端
dp[col] = prev + num;
}else { // 中間
dp[col] = Math.min(prev + num, curr + num);
}
prev = curr;
}
}
int minPath = dp[0];
for (int i = 1; i < m; i++) {
minPath = Math.min(minPath, dp[i]);
}
return minPath;
}
完全平方數(shù)
動(dòng)態(tài)規(guī)劃
- 如果是平方數(shù)还绘，則為1；
- 否則栖袋，為min(dp[i - 1 * 1], dp[i - 2 * 2], ...) + 1
public int numSquares(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i++){
if(isSqrt(i)){
dp[i] = 1;
}else {
int start = 1;
int min = i;
while (i - start * start > 0){
min = Math.min(dp[i - start * start] + 1, min);
start++;
}
dp[i] = min;
}
}
return dp[n];
}
public boolean isSqrt(int num){
int sqrt = (int) Math.sqrt(num);
return sqrt * sqrt == num;
}
數(shù)學(xué)
詳見leetcode的定理解說拍顷。
丑數(shù)
動(dòng)態(tài)規(guī)劃
public int nthUglyNumber(int n) {
int a = 0;
int b = 0;
int c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int n2 = dp[a] * 2;
int n3 = dp[b] * 3;
int n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if (dp[i] == n2) {
a++;
}
if (dp[i] == n3) {
b++;
}
if (dp[i] == n5) {
c++;
}
}
return dp[n - 1];
}
整數(shù)拆分
動(dòng)態(tài)規(guī)劃
public int integerBreak(int n) {
if (n < 3) {
return n - 1;
}
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
遞歸
暴力遞歸搜索
public int integerBreak(int n) {
if(n < 3){
return n-1;
}
int ans = 0;
for (int i = 1; i < n; i++) {
ans = Math.max(ans, Math.max(i * (n - i), i * integerBreak(n - i)));
}
return ans;
}
暴力超時(shí)原因是很多重復(fù)計(jì)算，于是加入緩存
// 緩存搜索
private int[] memory;
public int integerBreak(int n) {
memory = new int[n + 1];
return recursion(n);
}
public int recursion(int n) {
if (n < 3) {
return n - 1;
}
if (memory[n] > 0) {
return memory[n];
}
int res = 0;
for (int i = 1; i < n; i++) {
res = Math.max(res, Math.max(i * (n - i), i * recursion(n - i)));
}
memory[n] = res;
return res;
}
可被三整除的最大和
- 因?yàn)槊恳粚觗p的賦值會(huì)互相引用上一層的的值塘幅，所以需要加一個(gè)緩存變量dp2
public int maxSumDivThree(int[] nums) {
int[] dp = new int[]{0, Integer.MIN_VALUE, Integer.MIN_VALUE};
for (int n : nums) {
int[] dp2 = new int[3];
for (int i = 0; i < 3; i ++) {
int mod = n % 3;
dp2[i] = Math.max(dp[i], dp[(3 + i - mod) % 3] + n);
}
dp = dp2;
}
return dp[0];
}
打家劫舍 III
class Solution {
Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();
public int rob(TreeNode root) {
dfs(root);
return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.left);
dfs(node.right);
f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
}
}
空間優(yōu)化
public int rob(TreeNode root) {
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0], rootStatus[1]);
}
public int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
int selected = node.val + l[1] + r[1];
int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{selected, notSelected};
}
石子游戲
解決博弈問題的動(dòng)態(tài)規(guī)劃通用思路
package com.qiyun;
/**
* Created by qiyunsun on 2020/8/8.
*/
public class Solution {
class Pair {
int fir, sec;
Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec;
}
}
public boolean stoneGame(int[] piles) {
int n = piles.length;
// 初始化 dp 數(shù)組
Pair[][] dp = new Pair[n][n];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
dp[i][j] = new Pair(0, 0);
// 填入 base case
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// 斜著遍歷數(shù)組
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
// 先手選擇最左邊或最右邊的分?jǐn)?shù)
int left = piles[i] + dp[i + 1][j].sec;
int right = piles[j] + dp[i][j - 1].sec;
// 套用狀態(tài)轉(zhuǎn)移方程
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i + 1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j - 1].fir;
}
}
}
Pair res = dp[0][n - 1];
return res.fir - res.sec > 0;
}
}
新21點(diǎn)
動(dòng)態(tài)規(guī)劃之反序求解
class Solution {
public double new21Game(int N, int K, int W) {
if (K == 0) {
return 1.0;
}
double[] dp = new double[K + W];
for (int i = K; i <= N && i < K + W; i++) {
dp[i] = 1.0;
}
for (int i = K - 1; i >= 0; i--) {
for (int j = 1; j <= W; j++) {
dp[i] += dp[i + j] / W;
}
}
return dp[0];
}
}
優(yōu)化
上述計(jì)算中昔案，第二層for循環(huán)可以被優(yōu)化，因?yàn)槊恳淮蔚诙拥挠?jì)算相比上一次只有一個(gè)值的移動(dòng)电媳。
class Solution {
public double new21Game(int N, int K, int W) {
if (K == 0) {
return 1.0;
}
double[] dp = new double[K + W];
for (int i = K; i <= N && i < K + W; i++) {
dp[i] = 1.0;
}
dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
for (int i = K - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
}
return dp[0];
}
}
