----代碼隨想錄筆記
題型1含潘、基礎(chǔ)動態(tài)規(guī)劃
戰(zhàn)略：
基礎(chǔ)dp通常通過總結(jié)數(shù)學(xué)規(guī)律淀歇，如斐波拉契數(shù)列這種比較容易觀察到的規(guī)律潘懊。例題沒什么好說的姚糊，難以總結(jié)共性。
典型例題：
? 746. 使用最小花費(fèi)爬樓梯
? 509. 斐波那契數(shù)
? 70. 爬樓梯
? 62. 不同路徑
? 63. 不同路徑 II
? 343. 整數(shù)拆分
? 96. 不同的二叉搜索樹
題型2授舟、0-1背包
戰(zhàn)略：
0-1背包的原理需要掌握救恨，以及滾動數(shù)組的優(yōu)化。在做具體的題目释树，一般會有變形肠槽，以下是變形例子：
1、在背包容量限制下奢啥，能裝到的最大價值秸仙。這個是背包問題能直接套用的，但是要搞清楚題目中哪個是容量桩盲，哪個是價值寂纪，哪個是重量。
2、方案數(shù)捞蛋。是背包問題的經(jīng)典變形孝冒，是不能直接套用原背包遞推公式的。
經(jīng)典例題：
416. 分割等和子集
關(guān)鍵詞:
如果能夠分割成2個子集拟杉，那么一定存在子集和為數(shù)組之和的一半庄涡。
問題轉(zhuǎn)化：
在容量是（sum/2）的背包下，求能裝到的最大價值捣域，價值數(shù)組和重量數(shù)組都是nums啼染。因為最大的容量是（sum/2）,那么如果能夠分割成2個子集，最大容量是一定能夠填滿的焕梅。最后的判斷依據(jù)就是dp[capacity]==capatity?
細(xì)節(jié)：
如果sum/2不能被整除迹鹅，在nums是正整數(shù)的情況下，是可以直接返回false的贞言。
class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum%2!=0) {
return false;
}
int capacity = sum/2;
int[] dp = new int[capacity+1];
for (int i=0; i<nums.length; ++i) {
for (int j=capacity; j>=nums[i]; --j) {
dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
}
}
return dp[capacity]==capacity;
}
}
1049. 最后一塊石頭的重量 II
關(guān)鍵詞：
盡可能平分成2斜棚。換個方式理解，分成三堆a(bǔ),a,b该窗，其中2堆是重量一樣的弟蚀。total_weight = a+a+b, 如何使得b最小的問題，b>=0, 所以a最大取值是total_weight/2.
問題轉(zhuǎn)化：同416
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = Arrays.stream(stones).sum();
int capacity = sum/2;
int[] dp = new int[capacity+1];
for (int i=0; i<stones.length; ++i) {
for (int j=capacity; j>=stones[i]; --j) {
dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
}
}
return sum-dp[capacity]*2;
}
}
494. 目標(biāo)和
關(guān)鍵詞：
1酗失、方案數(shù)的求解問題义钉。
2、推導(dǎo)思路规肴，如果數(shù)組分成兩個部分捶闸，兩個部分的加和分別是a,b，那么有：
a-b=target
a+b=sum,sum為數(shù)組的和
所以a的值是可以確定的a=(sum+target)/2.
問題轉(zhuǎn)化：
本題是求方案數(shù)拖刃，個人感覺其實很難想到套用0-1背包删壮，原遞推公式是不可以直接套用的，方案數(shù)有自己的遞推公式兑牡，具體見代碼央碟。
細(xì)節(jié)：
1、對于target可能是負(fù)數(shù)均函，那么capacity也可能是負(fù)的亿虽，但是題中nums[i]>=0，所以capacity一定要是正的边酒。
2经柴、不能被整除的問題，類似416
3墩朦、dp的初始值問題坯认。與0-1背包不同，方案數(shù)都只與dp相關(guān)，如果沒有初始值牛哺，那么結(jié)果只能是0.
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum()+target;
if (sum%2!=0) {
// 都是整數(shù)陋气，不能湊成非整數(shù)
return 0;
}
int capacity = sum/2;
if (capacity<0) capacity = capacity;
int[] dp = new int[capacity+1];
dp[0]=1;
for (int i=0; i<nums.length; ++i) {
for (int j=capacity; j>=nums[i]; --j) {
dp[j] += dp[j-nums[i]];
}
}
return dp[capacity];
}
}
474. 一和零
關(guān)鍵詞：
非多重背包，因為每個元素只能使用一遍引润，這個是2維的0-1背包巩趁。
問題轉(zhuǎn)化：
直接套用0-1背包遞推公式，搞清楚以下問題：
重量是什么淳附？每個元素的0议慰，1個數(shù)
價值是什么？元素的個數(shù)奴曙，能放進(jìn)背包的即+1
容量是什么别凹？m，n
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[] count0 = new int[strs.length];
int[] count1 = new int[strs.length];
for (int i=0; i<strs.length; ++i) {
String str = strs[i];
for (int j=0; j<str.length(); ++j) {
if (str.charAt(j)=='0') {
count0[i]++;
} else {
count1[i]++;
}
}
}
int[][] dp = new int[m+1][n+1];
for (int i=0; i<strs.length; ++i) {
for (int x=m; x>=count0[i]; --x) {
for (int y=n; y>=count1[i]; --y) {
dp[x][y] = Math.max(dp[x][y],dp[x-count0[i]][y-count1[i]]+1);
}
}
}
return dp[m][n];
}
}
以上代碼可以優(yōu)化成：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for (int i=0; i<strs.length; ++i) {
String str = strs[i];
int zeroNum = 0;
int oneNum = 0;
for (char ch:str.toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
for (int x=m; x>=zeroNum; --x) {
for (int y=n; y>=oneNum; --y) {
dp[x][y] = Math.max(dp[x][y], dp[x-zeroNum][y-oneNum]+1);
}
}
}
return dp[m][n];
}
}
題型3洽糟、完全背包
戰(zhàn)略：
完全背包的原理炉菲，換元的推導(dǎo)方法，以及滾動數(shù)組的優(yōu)化坤溃。具體的題目有以下變形：
1拍霜、直接套用完全背包的公式。
2薪介、方案數(shù)祠饺，方案數(shù)有又分組合數(shù)和排序數(shù)，組合是先背包后容量汁政。排序數(shù)是先容量后背包吠裆。
3、利用換元法推導(dǎo)出來的烂完。這種感覺都不像是背包問題了。
經(jīng)典例題：
518. 零錢兌換 II
關(guān)鍵詞：
1.組合方案數(shù)
問題轉(zhuǎn)化：
無論是0-1诵棵，還是完全抠蚣，方案數(shù)的遞推公式是dp[j]+=dp[j]+dp[j-nums[i]
推導(dǎo)過程：
dp[i][j] , 到第i個數(shù)位置，價值為j的方案數(shù)有dp[i][j]個
dp[i][j] = dp[i-1][j-k*nums[i]]
dp[i][j-nums[i]] = dp[i-1][j-(k+1)*nums[i]]
dp[i][j] = dp[i-1][j] + dp[i][j-nums[i]]
降維優(yōu)化：和完全背包的思路一樣履澳，不寫了嘶窄。結(jié)果是：dp[j] = dp[j] + dp[j-nums[i]]
細(xì)節(jié)：
1、與0-1相似距贷，方案數(shù)一定要初始話dp[0] = 1; 方案數(shù)完全通過dp轉(zhuǎn)的柄冲，所以如果沒有初始化，結(jié)果一定是0.
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=coins[i]; j<=amount; ++j) {
dp[j] = dp[j] + dp[j-coins[i]];
}
}
return dp[amount];
}
}
377. 組合總和 Ⅳ
關(guān)鍵詞：
1忠蝗、排序方案數(shù)
問題轉(zhuǎn)化：
與518不一樣的是现横，518不用考慮順序，而此題需要。
例子：
如果是零錢{2,3}, 組合成5的方式有戒祠，如果是518那么就是1骇两，而此題則為2.
為什么for循環(huán)的先后順序會有兩種不同的結(jié)果呢？以??的例子分析姜盈。i是背包低千，j是容量。
組合：先背包后容量
倒數(shù)第2次遍歷馏颂，i=0示血，j=2～5，這個循環(huán)結(jié)束后救拉，dp = {1,0,1,0,1,0}, 單從含義來理解难审，就是到2這個數(shù)位置，組成0近上，2剔宪，4分別有一種方式，其他為0.
最后一次遍歷壹无，i=1葱绒，j=3～5，j=4時斗锭，dp={1,0,1,1,1,0}, j=5時地淀，dp={1,0,1,1,1,1}, dp[5]的位置只被計算了一遍。
排序：先容量后背包
倒數(shù)第2次外循環(huán)遍歷岖是，j=4帮毁，i=0～1，這個外循環(huán)結(jié)束后豺撑，dp={1,0,1,1,1,0}烈疚，單從含義理解躯概，就是到3這個數(shù)鹰椒，組合成0洼滚，2洞斯，3轮纫，4分別有1種方法胰丁。
最后一次外循環(huán)遍歷妇押，j=5拭宁，i=0～1音瓷，在這個循環(huán)中对嚼，可以看到dp[5]的位置被計算了兩遍，先加上了dp[2],后加上了dp[3]绳慎。先加了dp[2]纵竖，表示組合為2的方案數(shù)之后自己補(bǔ)3漠烧；再加上了dp[3]，表示組合為3的方案數(shù)之后自己補(bǔ)2磨确，從這里看出來沽甥，排序方案數(shù)時不在乎順序的；而組合方案數(shù)只考慮了加上dp[3]乏奥，后面自己補(bǔ)2摆舟。
———
感覺這里關(guān)于順序的思考還沒有觸達(dá)本質(zhì)，后面再想想吧邓了。
細(xì)節(jié)：
1恨诱、求方案數(shù)要初始化，第三遍了～
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for (int j=1; j<=target; ++j) {
for(int i=0; i<nums.length; ++i) {
if (j>=nums[i]) {
dp[j] = dp[j] + dp[j-nums[i]];
}
}
}
return dp[target];
}
}
322. 零錢兌換
關(guān)鍵詞：
1骗炉、求min的推導(dǎo)照宝，類似完全背包問題
問題轉(zhuǎn)化：
推導(dǎo)過程：
dp[i][j]:到第i個數(shù)為止，組合成j的硬幣的個數(shù)
dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+1, dp[i-1][j-2v[i]]+2, ···)
dp[i][j-v[i]] = min(dp[i-1][j-v[i]], dp[i-1][j-2v[i]]+1, dp[i-1][j-3*v[i]]+2, ···)
dp[i][j] = min(dp[i-1][j], dp[i][j-v[i]]+1);
細(xì)節(jié)：
1句葵、初始化問題厕鹃，因為是求min的，所以要初始化為最大值占位乍丈，這個站位可以認(rèn)為找不到方案剂碴，又因為dp[0]是推導(dǎo)的開始，所以要初始化為一個有意義的值轻专，dp[0]=0
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i=0; i<coins.length; ++i) {
for (int j=coins[i]; j<=amount; ++j) {
if (dp[j - coins[i]] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1:dp[amount];
}
}
279. 完全平方數(shù)
類似322忆矛，跳過
139. 單詞拆分
關(guān)鍵詞：dp定義+推導(dǎo)
問題轉(zhuǎn)化：
這一題感覺不是很想背包，和322一樣请垛，推導(dǎo)的過程中和背包很像催训。
推導(dǎo)：
dp[i]:字符串前i個字符能否被拆分
dp[i+1]的遞推：
dp[0]==true && 0～i（包含i）是否存在字典數(shù)組中 或
dp[1]==true && 1～i（包含i）是否存在字典數(shù)組中 或
···
dp[i]==true && i～i(包含i) 是否存在字典數(shù)組中
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int i=1; i<dp.length; ++i) {
for (int j=0; j<i; ++j) {
String tmp = s.substring(j, i);
if (wordDict.contains(tmp) && dp[j] == true) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
題型4、打家劫舍
戰(zhàn)略：
每家有且只有2種選擇宗收，偷or不偷漫拭，所以要有2維數(shù)組來存儲狀態(tài)。在遍歷順序上混稽，根據(jù)前面的值算出當(dāng)前值嫂侍。
經(jīng)典例題
198. 打家劫舍
關(guān)鍵詞：
class Solution {
public int rob(int[] nums) {
int[][] dp = new int[2][nums.length];
dp[0][0] = 0;
dp[1][0] = nums[0];
for (int i=1; i<nums.length; ++i) {
dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
dp[1][i] = dp[0][i-1]+nums[i];
}
return Math.max(dp[0][nums.length-1], dp[1][nums.length-1]);
}
}
213. 打家劫舍 II
關(guān)鍵詞：
1、環(huán)形荚坞，類似于滑動窗口的思想，固定長度的窗口菲盾，只考慮窗口內(nèi)部的
class Solution {
public int rob(int[] nums) {
if (nums.length==1) {
return nums[0];
}
if (nums.length==2) {
return Math.max(nums[0], nums[1]);
}
int result1 = robWithInterval(nums, 1, nums.length-2);
int result2 = robWithInterval(nums, 2, nums.length-1);
return Math.max(result1, result2);
}
public int robWithInterval(int[] nums, int start, int end) {
if (start>end) {
return 0;
}
int[][] dp = new int[2][nums.length];
dp[0][start-1] = 0;
dp[1][start-1] = nums[start-1];
for (int i=start; i<=end; ++i) {
dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
dp[1][i] = dp[0][i-1]+nums[i];
}
return Math.max(dp[0][end], dp[1][end]);
}
}
337. 打家劫舍 III
關(guān)鍵詞：
1颓影、后序遍歷
2、依舊需要2維數(shù)組來表示狀態(tài)懒鉴，2維數(shù)組包含了2個信息诡挂，一個是下標(biāo)表示是否偷碎浇，一個是值表示偷到的金額
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = robDfs(root);
return Math.max(res[0], res[1]);
}
public int[] robDfs(TreeNode root) {
int[] res = new int[2];
if (root==null) {
return res;
}
int[] left = robDfs(root.left);
int[] right = robDfs(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = left[0]+right[0]+root.val;
return res;
}
}
題型5、股票買賣
戰(zhàn)略：
需要用數(shù)組來表示不同狀態(tài)下的股票情況璃俗，這點和打家劫舍類似奴璃。數(shù)組的狀態(tài)主要有一下幾種：
1、持有城豁、不持有苟穆，這里有個問題：如果當(dāng)天賣掉了，算持有嗎唱星？--不算雳旅。這種分法主要是只有對買賣的次數(shù)沒有要求。
2间聊、如果對買賣的次數(shù)有要求攒盈，就要明確是第幾次買賣。
3哎榴、冷凍期的情況型豁，就要分成：買入、賣出尚蝌、冷凍這3中情況迎变。
經(jīng)典例題：
121. 買賣股票的最佳時機(jī)
關(guān)鍵詞：
1、只能買賣一次
問題轉(zhuǎn)化：
是戰(zhàn)略里面的第一種驼壶，需要記錄2種狀態(tài)
細(xì)節(jié)
只能買賣一次氏豌，怎么體現(xiàn)這個一次？下一題講到热凹。
122. 買賣股票的最佳時機(jī) II
關(guān)鍵詞：
1泵喘、可以買賣多次，對次數(shù)不做要求
問題轉(zhuǎn)化：
是戰(zhàn)略里面的第一種
細(xì)節(jié)：
和121的區(qū)別在于般妙，持有的計算需要建立在i-1天不持有的基礎(chǔ)上纪铺，二只能買賣一次不需要。
714. 買賣股票的最佳時機(jī)含手續(xù)費(fèi)
關(guān)鍵詞：
1碟渺、賣出的時候減掉手續(xù)費(fèi)
問題轉(zhuǎn)化：
是戰(zhàn)略里面的第一種鲜锚，本質(zhì)上和121沒有太大區(qū)別。
123. 買賣股票的最佳時機(jī) III
關(guān)鍵詞：
1苫拍、限制次數(shù)
問題轉(zhuǎn)化：
是戰(zhàn)略里面的第二種芜繁，有一下5種狀態(tài)：
沒有操作
第一次買入
第一次賣出
第二次買入
第二次賣出
細(xì)節(jié)
初始化的問題，第一天绒极，第2次買入可以理解在第一天買入-賣出-買入骏令。
188. 買賣股票的最佳時機(jī) IV
關(guān)鍵詞：
1、限制次數(shù)
問題轉(zhuǎn)化
是123的抽象版
309. 最佳買賣股票時機(jī)含冷凍期
關(guān)鍵詞：
1垄提、冷凍期
問題轉(zhuǎn)化：
是戰(zhàn)略里面的第三種榔袋。
題型6周拐、子序列
戰(zhàn)略：
1、一定要確定dp數(shù)組的定義凰兑，下標(biāo)和值各有定義妥粟。
關(guān)于定義，我怎么知道要怎么定義呢吏够？
a.如果題目要求是遞增或者遞減, 不管是否有子序列是否連續(xù)的要求勾给，一般都要定義為：以第i個結(jié)尾的最長子序列的長度是dp[i].一般dp種的最大值是所求。
b.如果題目要求子序列不連續(xù)：遍歷到第i個為止（不一定以i結(jié)尾）的子序列的長度是dp[i].一般dp[length-1]就是所求稿饰。
c.如果題目要求子序列連續(xù)：以第i個結(jié)尾的連續(xù)子序列的長度是dp[i].一般dp種的最大值是所求锦秒。
注意以上b，c兩種區(qū)別喉镰，它們的遞推公式差異也很大旅择。
如果是b，一般是和遍歷到的所有都有關(guān)系侣姆，一般是max（xxx）這種生真。
如果是c，一般只和dp[i-1]相關(guān)捺宗。
2柱蟀、確定遞推公式的時候，要學(xué)會怎么劃分蚜厉，要做到不重不漏长已，但是有例外，就是求min昼牛，max的情況下术瓮，重復(fù)不會影響結(jié)果的。但是最好還是按照不重不漏的標(biāo)準(zhǔn)來劃分情況贰健，然后推導(dǎo)公式胞四。
經(jīng)典例題：
300. 最長遞增子序列
關(guān)鍵詞：
1、遞增
2伶椿、不連續(xù)
3辜伟、dp定義，dp[i]表示i之前包括i的以nums[i]結(jié)尾最長上升子序列的長度
問題轉(zhuǎn)化：
因為要求是遞增的脊另，所以采用戰(zhàn)略中的第一種导狡，需要明確知道上個末尾的數(shù)字是多少。
細(xì)節(jié)：
數(shù)組初始化為1
674. 最長連續(xù)遞增序列
關(guān)鍵詞：
1偎痛、遞增
2烘豌、連續(xù)
3、dp定義
問題轉(zhuǎn)化：
因為要求遞增看彼，而且是連續(xù)的廊佩，所以不管從哪個角度，dp定義都是：dp[i]：以下標(biāo)i為結(jié)尾的數(shù)組的連續(xù)遞增的子序列長度為dp[i]靖榕。
細(xì)節(jié)：
數(shù)組初始化為1
718. 最長重復(fù)子數(shù)組
關(guān)鍵詞:
1标锄、連續(xù)
2、dp定義
問題轉(zhuǎn)化：
沒有要求是遞增或者遞減茁计，所以看是否連續(xù)料皇，這里題目的要求是連續(xù)的，是戰(zhàn)略里面的c星压。
實現(xiàn)細(xì)節(jié):
初始化第一行践剂，第一列要注意，但是單獨拿出來娜膘，代碼不好看逊脯，所以在初始化dp數(shù)組的時候，dp[length+1]竣贪，把長度+1军洼，遍歷的時候從1
開始，就不用特地初始首行首列演怎。
1143. 最長公共子序列
關(guān)鍵詞：
1匕争、不連續(xù)
2、dp定義
問題轉(zhuǎn)化：
沒有要求是遞增或者遞減爷耀，所以看是否連續(xù)甘桑，這里題目的要求是不連續(xù)的，是戰(zhàn)略里面的b歹叮∨芎迹可以堪稱是300題的升維處理。
實現(xiàn)細(xì)節(jié)：
還是要注意首行首列的初始化盗胀，巧妙的做法如718題艘蹋。
1035. 不相交的線
關(guān)鍵詞：
1、就是求公共子序列
問題轉(zhuǎn)化：
有點像應(yīng)用題票灰，其實和1143是一樣的女阀，代碼實現(xiàn)也一樣。
392. 判斷子序列
關(guān)鍵詞：
1屑迂、求公共子序列的變形浸策，只要長度和s一致就好了
問題轉(zhuǎn)化：
也像應(yīng)用題，其實本質(zhì)和1143一樣惹盼，代碼稍作改動庸汗。
583. 兩個字符串的刪除操作
關(guān)鍵詞：
1、最小值
問題轉(zhuǎn)化：
是求公共子序列的變形手报，所以先要確定dp蚯舱，dp[i][j],word1長度是i改化，word2長度是j，需要達(dá)到相等枉昏，所需要刪除元素的最少次數(shù)陈肛。
實現(xiàn)細(xì)節(jié)：
dp長度還是length+1，但是這里的首行首列需要初始化了兄裂，它是有意義的句旱。
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
for (int i = 1; i < word1.length() + 1; i++) {
for (int j = 1; j < word2.length() + 1; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // 相等，可以作為公共子序列的一部分晰奖，所以不需要額外的操作
}else{
dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)); // 不可以作為公共子序列的一部分谈撒，只能刪掉了
}
}
}
return dp[word1.length()][word2.length()];
}
}
53. 最大子數(shù)組和
關(guān)鍵詞：
1、連續(xù)
問題轉(zhuǎn)化：
不要求遞增匾南，但是要求連續(xù)啃匿，是戰(zhàn)略中c的類別。dp定義：dp[i]：以第i個數(shù)結(jié)尾的最大連續(xù)子序列和為dp[i]午衰。
115. 不同的子序列
關(guān)鍵詞：
問題轉(zhuǎn)化：
這一題比較特別立宜，感覺不是很好套模型。先給出dp定義
注意這里不考慮實現(xiàn)細(xì)節(jié)的優(yōu)化ｋ丁３仁！
dp[i][j]：以i為結(jié)尾的s子序列中出現(xiàn)以j為結(jié)尾的t的個數(shù)為dp[i][j]帅戒。
- s[i]==t[j]灯帮，
- s[i]!=t[j], 那么t(0j)出現(xiàn)在s(0i)中的次數(shù)，和出現(xiàn)在(0~i-1)中一樣的逻住。比如t=ab钟哥，s=abc，當(dāng)j=1瞎访， i=2時腻贰。
實現(xiàn)細(xì)節(jié)：
init dp長度是length+1, 同時注意首列的初始化為1
class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i < s.length() + 1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < t.length() + 1; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.length()][t.length()];
}
}
