動(dòng)態(tài)規(guī)劃（DP）
1.最大子序和（leetcode 53 S.）
給定一個(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煤杀。
常規(guī)：
class Solution {
public int maxSubArray(int[] nums) {
//定義和
int sum = 0;
//這里的j沒(méi)必要了
int j = 0;
//令最大初始值為int的最小值
int max = Integer.MIN_VALUE;
for(int i=0;i<nums.length;++i){
j = i;
//如果i個(gè)連續(xù)和比第i個(gè)元素小，說(shuō)明前i-1個(gè)元素不可能為最大和最大和為nums[i]
if(sum + nums[j] < nums[j]){
sum = nums[j];
}else{
//若前i個(gè)連續(xù)和大于等于第i個(gè)元素谒出，最大和為前i個(gè)元素相加
sum += nums[j];
}
//如果當(dāng)前最大和比max大
if(sum > max){
max = sum;
}
}
return max;
}
}
DP:
class Solution {
public int maxSubArray(int[] nums) {
//最大和數(shù)組
int[] dp = new int[nums.length];
//一個(gè)元素最大和為當(dāng)前元素
dp[0] = nums[0];
int temp = nums[0];
for(int i = 1;i < nums.length;++i){
//這里發(fā)現(xiàn)用Math.max()函數(shù)效率低
if(dp[i - 1] + nums[i] < nums[i]){
dp[i] = nums[i];
}else{
dp[i] = dp[i - 1] + nums[i];
}
//dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
if(temp < dp[i]){
temp = dp[i];
}
//temp = Math.max(dp[i],temp);
}
return temp;
}
}
2.爬樓梯（leetcode 70 S.）
假設(shè)你正在爬樓梯隅俘。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階笤喳。你有多少種不同的方法可以爬到樓頂呢为居？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂杀狡。
1 階 + 1 階
2 階
示例 2：
輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂蒙畴。
1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階
分析：
假如n = 10,要想爬到樓頂，要么從第九層爬一個(gè)臺(tái)階上去呜象，要么從第八層爬兩個(gè)臺(tái)階上去
此時(shí)我們假設(shè)F(n) = 爬到第n層臺(tái)階有多少種方法
通過(guò)上面的分析我們知道爬到第十層的方法是第九層和第八層的和
也即 我們得到遞推式F(n) = F(n - 1) + F(n - 2)
由遞推式我們立馬想到了用遞歸 首先找到終止條件
當(dāng)只有一層樓梯的時(shí)候我們爬一層即可到達(dá)樓頂膳凝，即 F(1) = 1
當(dāng)只有兩層的時(shí)候我們可以一層一層的爬，也可以直接爬兩層恭陡，即F(2) = 2
遞歸：
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
}
這里可以看出當(dāng)n很大時(shí)遞歸深度很深蹬音，時(shí)間復(fù)雜度為指數(shù)級(jí)別，導(dǎo)致超時(shí)子姜，這里我們觀(guān)察到climbStairs(n-2),climbStairs(n-3)....被調(diào)用的多次祟绊，如果我們可以找個(gè)容器將他的值存儲(chǔ)下來(lái)楼入，下次遇到的時(shí)候判斷容器里面是否有這個(gè)函數(shù)的值，如果有直接拿出來(lái)用牧抽，如果沒(méi)有計(jì)算以后把它放到容器中嘉熊。
這種算法叫做備忘錄算法
備忘錄算法：
class Solution {
Map<Integer,Integer> map = new HashMap<>();
public int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
if(map.containsKey(n)){
return map.get(n);
}
int value = climbStairs(n-1) + climbStairs(n-2);
map.put(n,value);
return value;
}
}
但是使用備忘錄算法算法時(shí)間復(fù)雜度還是很高，能不能不使用遞歸扬舒，這里我們正向思考
從第一層樓梯可以到達(dá)第二層或者第三層阐肤，第二層可以到達(dá)第三層或者第四層....以此類(lèi)推
| dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | ... |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 5 | 8 | ... |
觀(guān)察得知dp[i] = dp[i-1] + dp[i-2],i>=3
DP:
class Solution {
public int climbStairs(int n) {
//dp數(shù)組存放的是到達(dá)第n層共有多少方法
int[] dp = new int[n+1];
dp[1] = 1;
if(n > 1){
dp[2] = 2;
}
for(int i = 3;i <= n;++i){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
此時(shí)時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(n) 我們能不能優(yōu)化空間？
由觀(guān)察得：dp[i] = dp[i-1] + dp[i-2] 只與前兩個(gè)數(shù)有關(guān)讲坎，那么我們沒(méi)有必要存儲(chǔ)所有的數(shù)了
優(yōu)化DP:
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
//初始值
int a = 1;
int b = 2;
//temp代替數(shù)組
int temp;
for(int i = 3;i <= n;++i){
temp = a;
a = b;
b = b + temp;
}
return b;
}
}
3.買(mǎi)賣(mài)股票的最佳時(shí)機(jī)（leetcode 121 S.）
給定一個(gè)數(shù)組孕惜，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易（即買(mǎi)入和賣(mài)出一支股票）晨炕，設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)衫画。
注意你不能在買(mǎi)入股票前賣(mài)出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入瓮栗，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出削罩，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格费奸。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0弥激。
分析：
觀(guān)察題目我們知道一般有兩個(gè)狀態(tài)，手中有股票和手中無(wú)股票愿阐，我們記作0和1.
dp[0]表示手中無(wú)股的最大利潤(rùn)微服，這里分為兩種情況，第一種是沒(méi)有買(mǎi)也沒(méi)有賣(mài)缨历，這是利潤(rùn)為0以蕴，第二種情況是買(mǎi)賣(mài)結(jié)束了
dp[1]表示手中有股票
DP：
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
int[] dp = new int[2];
dp[0] = 0;
dp[1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]);
dp[1] = Math.max(dp[1], -prices[i]);
}
return dp[0];
}
4.打家劫舍（leetcode 198 S.）
你是一個(gè)專(zhuān)業(yè)的小偷，計(jì)劃偷竊沿街的房屋戈二。每間房?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 。
分析：
題目意思就是假如我偷了第一家，就不能偷第二家只能偷第三家桩皿、第四家...
若總共有10戶(hù)人家豌汇，偷10戶(hù)人家的最高金額就分為
1.偷了第九戶(hù)人家（肯定不能偷第10戶(hù)了）
2.沒(méi)有偷第九戶(hù)人家（這是可以偷第八戶(hù)）
這時(shí)候要求出兩種方式的最大值
得到關(guān)系式：
記第i戶(hù)人家的金額是cost[i]
F(n) = max(F(n-1),F(n-2) + cost[n])
DP:
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int[] dp = new int[nums.length + 1];
dp[0] = nums[0];
if(nums.length > 1){
dp[1] = Math.max(nums[0],nums[1]);
}
for(int i = 2;i < nums.length;++i){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
}
return dp[nums.length-1];
}
}
cost數(shù)組：
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 2 | 7 | 9 | 3 | 1 |
dp數(shù)組：
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 2 | 7 | 11 | 11 | 12 |
這里我們觀(guān)察結(jié)果只與前兩個(gè)有關(guān)，我們可以定義臨時(shí)變量存儲(chǔ)優(yōu)化空間為O(1)
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int a = nums[0];
if(nums.length == 1)
return a;
int b = Math.max(nums[0],nums[1]);
int temp;
for(int i = 2;i < nums.length;++i){
temp = a;
a = b;
b = Math.max(temp + nums[i],b);
}
return b;
}
}
5.區(qū)域檢索-數(shù)組不可變（leetcode 303 S.）
給定一個(gè)整數(shù)數(shù)組 nums泄隔，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內(nèi)元素的總和拒贱，包含 i, j 兩點(diǎn)。
示例：
給定 nums = [-2, 0, 3, -5, 2, -1]佛嬉，求和函數(shù)為 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
說(shuō)明:
你可以假設(shè)數(shù)組不可變逻澳。
會(huì)多次調(diào)用 sumRange 方法。
分析：
本題可以采用暴力求解暖呕，但是需要多次調(diào)用效率很低
那么可以在求解之前把所有的sumRange(0, i) i<=n 求出來(lái) 存放在dp數(shù)組中
所以
sumRange(0, 2) = dp[2];
sumRange(2, 5) = dp[5] - dp[1];
所以
sumRange(i, j) = dp[j] - dp[i-1] (i != 0)
sumRange(i, j) = dp[j] (i == 0)
DP:
class NumArray {
int[] dp;
public NumArray(int[] nums) {
dp = new int[nums.length];
if(nums.length > 0){
dp[0] = nums[0];
}
for(int i = 1;i < nums.length;++i){
dp[i] = dp[i-1] + nums[i];
}
}
public int sumRange(int i, int j) {
return (i == 0) ? dp[j] : dp[j] - dp[i-1];
}
}
6.判斷子序列（leetcode 392 S.）
給定字符串 s 和 t 斜做，判斷 s 是否為 t 的子序列。
你可以認(rèn)為 s 和 t 中僅包含英文小寫(xiě)字母湾揽。字符串 t 可能會(huì)很長(zhǎng)（長(zhǎng)度 ~= 500,000）陨享，而 s 是個(gè)短字符串（長(zhǎng)度 <=100）。
字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串钝腺。（例如抛姑，"ace"是"abcde"的一個(gè)子序列，而"aec"不是）艳狐。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
分析：
定義dp[i] [j] 表示i個(gè)s是否是j個(gè)t的子序列
class Solution {
public boolean isSubsequence(String s, String t) {
int sLen = s.length();
int tLen = t.length();
if(sLen == 0)
return true;
boolean[][] dp = new boolean[sLen+1][tLen+1];
for(int j = 0;j < tLen;++j){
dp[0][j] = true;
}
for(int i = 1;i <= sLen;++i){
for(int j = 1;j <= tLen;++j){
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[sLen][tLen];
}
}
本題使用DP效率是非常低的不是最優(yōu)解
這里有個(gè)小小的優(yōu)化
可以遍歷s字符串 從t中查找 這里查到的index必須是越來(lái)越大的定硝，如果index == -1那么匹配失敗
代碼：
class Solution {
public boolean isSubsequence(String s, String t) {
int index = 0;
for(int i = 0; i < s.length();++i){
if(t.indexOf(String.valueOf(s.charAt(i)),index) != -1){
index = t.indexOf(String.valueOf(s.charAt(i)),index) + 1;
continue;
}
return false;
}
return true;
}
}
7.使用最小花費(fèi)爬樓梯（leetcode 746 S.）
數(shù)組的每個(gè)索引做為一個(gè)階梯，第 i個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值 cost[i] (索引從0開(kāi)始)毫目。
每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力花費(fèi)值蔬啡，然后你可以選擇繼續(xù)爬一個(gè)階梯或者爬兩個(gè)階梯。
您需要找到達(dá)到樓層頂部的最低花費(fèi)镀虐。在開(kāi)始時(shí)箱蟆，你可以選擇從索引為 0 或 1 的元素作為初始階梯。
示例 1:
輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費(fèi)是從cost[1]開(kāi)始刮便，然后走兩步即可到階梯頂空猜，一共花費(fèi)15。
示例 2:
輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費(fèi)方式是從cost[0]開(kāi)始恨旱，逐個(gè)經(jīng)過(guò)那些1辈毯，跳過(guò)cost[3]，一共花費(fèi)6搜贤。
注意：
cost 的長(zhǎng)度將會(huì)在 [2, 1000]谆沃。
每一個(gè) cost[i] 將會(huì)是一個(gè)Integer類(lèi)型，范圍為 [0, 999]仪芒。
分析：
到達(dá)樓頂有兩種方法
第一種從第一層開(kāi)始到達(dá)樓頂
第二種從第二層開(kāi)始到達(dá)樓頂
記dp[i]為從第i層到達(dá)樓頂
終點(diǎn)是從最后一層或者倒數(shù)第二層
這里可以得到關(guān)系式
dp[i] = cost[i] + min(dp[i+1],dp[i+2]) 這里的i是遞減的
最終得到的結(jié)果就是dp[0]和dp[1]中最小的那個(gè)
代碼：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[len-1] = cost[len-1];
dp[len-2] = cost[len-2];
for(int i = len-3;i >= 0;--i){
dp[i] = cost[i] + Math.min(dp[i+1],dp[i+2]);
}
return Math.min(dp[0],dp[1]);
}
}
8.除數(shù)博弈（leetcode 1025 S.）
愛(ài)麗絲和鮑勃一起玩游戲唁影，他們輪流行動(dòng)耕陷。愛(ài)麗絲先手開(kāi)局。
最初据沈，黑板上有一個(gè)數(shù)字 N 啃炸。在每個(gè)玩家的回合，玩家需要執(zhí)行以下操作：
選出任一 x卓舵，滿(mǎn)足 0 < x < N 且 N % x == 0 南用。
用 N - x 替換黑板上的數(shù)字 N 。
如果玩家無(wú)法執(zhí)行這些操作掏湾，就會(huì)輸?shù)粲螒颉?/p>
只有在愛(ài)麗絲在游戲中取得勝利時(shí)才返回 True裹虫，否則返回 false。假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲融击。
示例 1：
輸入：2
輸出：true
解釋?zhuān)簮?ài)麗絲選擇 1筑公，鮑勃無(wú)法進(jìn)行操作。
示例 2：
輸入：3
輸出：false
解釋?zhuān)簮?ài)麗絲選擇 1尊浪，鮑勃也選擇 1匣屡，然后愛(ài)麗絲無(wú)法進(jìn)行操作。
提示：
1 <= N <= 1000
9.最長(zhǎng)回文子串（leetcode 5 M.）
給定一個(gè)字符串 s拇涤，找到 s 中最長(zhǎng)的回文子串捣作。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案鹅士。
示例 2：
輸入: "cbbd"
輸出: "bb"
分析：
最優(yōu)子結(jié)構(gòu)問(wèn)題很容易想到動(dòng)態(tài)規(guī)劃
1.確定狀態(tài)
2.找到狀態(tài)轉(zhuǎn)移方程
3.確定初值
確定狀態(tài)
定義dp[] []二維數(shù)組券躁，其中dp[i] [j]表示s串從i~j是否是回文
回文定義：一個(gè)字符串正著遍歷和反著遍歷結(jié)果相同那么該串就是回文串
例如：“aba”,"aa"是回文串，“abc”,"ab"就不是回文串
所以如果dp[i] [j]是回文串那么dp[i+1] [j-1]也一定是回文串
找到狀態(tài)轉(zhuǎn)移方程
如果s是空串 那么s本身就是回文串
當(dāng)s[i] == s[j]時(shí)
如果i掉盅，j中只有一個(gè)字符也拜，或者沒(méi)有字符那么該串一定是回文串（j - i <=2）
否則判斷i+1~j-1是不是回文（dp[i+1] [j-1] == true）那么該串也是回文串
如果該回文串的長(zhǎng)度比之前記錄的大那么該回文串為最大
代碼：
class Solution {
public String longestPalindrome(String s) {
if(s.length() <= 1)
return s;
int len = s.length();
boolean[][] dp = new boolean[len][len];
int max = 1;
String res = s.substring(0,1);
for(int j = 1;j < len;++j){
for(int i = 0;i < j;++i){
//或運(yùn)算的短路
if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i+1][j-1])){
dp[i][j] = true;
if(j - i + 1 > max){
max = j - i + 1;
res = s.substring(i,j+1);
}
}
}
}
return res;
}
}
10.不同路徑（leetcode 62 M.）
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步趾痘。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）慢哈。
問(wèn)總共有多少條不同的路徑？
例如永票，上圖是一個(gè)7 x 3 的網(wǎng)格卵贱。有多少可能的路徑？
說(shuō)明：m 和 n 的值均不超過(guò) 100瓦侮。
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開(kāi)始艰赞，總共有 3 條路徑可以到達(dá)右下角佣谐。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
分析：
確定狀態(tài)
定義dp數(shù)組肚吏，dp[i] [j]表示從起點(diǎn)到（i，j）共有多少路徑狭魂。所以dp[m-1] [n-1]就是答案
找到狀態(tài)轉(zhuǎn)移方程
由于機(jī)器人只能向右或者向下走所以機(jī)器人只有從（i-1罚攀，j）或者（i,j-1）才能到達(dá)（i党觅，j）
所以狀態(tài)轉(zhuǎn)移方程為：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1];
確定初值
由狀態(tài)轉(zhuǎn)移方程我們無(wú)法算出dp[0] [j] 和dp[i] [0]的值，由觀(guān)察知機(jī)器人到達(dá)dp[0] [j] 和dp[i] [0]均只有一條路徑斋泄，那就是向右一直走杯瞻，或者向下一直走
所以初值為：dp[i] [0] = 1;dp[0] [j] = 1;
代碼：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0;i < m;++i){
dp[i][0] = 1;
}
for(int i = 0;i < n;++i){
dp[0][i] = 1;
}
for(int i = 1;i < m;++i){
for(int j = 1;j < n;++j){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
這時(shí)候時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度O(n^2)可以?xún)?yōu)化空間復(fù)雜度為O(n)
dp[i] [j] 只與dp[i-1] [j] 和dp[i] [j-1]有關(guān)所以只需要定義一維數(shù)組即可
代碼：
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[m];
for(int i = 0;i < m;++i){
dp[i] = 1;
}
for(int j = 1;j < n;++j){
for(int i = 1; i < m;++i){
dp[i] = dp[i-1] + dp[i];
}
}
return dp[m-1];
}
}
11.不同路徑Ⅱ（leetcode 63 M.）
一個(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 來(lái)表示。
說(shuō)明：m 和 n 的值均不超過(guò) 100痹束。
示例 1:
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個(gè)障礙物检疫。
從左上角到右下角一共有 2 條不同的路徑：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
分析：
本題與上一題最大的區(qū)別在于加了一個(gè)障礙物，意思也就是經(jīng)過(guò)障礙物到達(dá)終點(diǎn)的點(diǎn)全部無(wú)效
確定狀態(tài)
記障礙物數(shù)組為a[] []祷嘶，這里可以直接在障礙物數(shù)組進(jìn)行修改a[i] [j]表示到（i屎媳，j）的方案數(shù)
找到狀態(tài)轉(zhuǎn)移方程
如果a[i] [j] = 1說(shuō)明該處是障礙物不可到達(dá)，a[i] [j] = 0
否則該處可到達(dá)并且方案數(shù)a[i] [j] = a[i-1] [j] + a[i] [j-1]
確定初值
我們知道邊界的情況下a[i] [0]或者a[0] [j] 取決于a[i-1] [0] 和a[0] [j]
也就是a[i] [0] = a[i-1] [0]; a[0] [j] = a[0] [j-1];
這里還需要考慮一個(gè)起點(diǎn)论巍，如果起點(diǎn)是障礙物那么返回0
如果a[0] [0] = 0 那么a[0] [0] = 1;
代碼：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid[0][0] == 1){
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
obstacleGrid[0][0] = 1;
for(int i = 1;i < m;++i){
if(obstacleGrid[i][0] == 1){
obstacleGrid[i][0] = 0;
continue;
}
obstacleGrid[i][0] = obstacleGrid[i-1][0];
}
for(int i = 1;i < n;++i){
if(obstacleGrid[0][i] == 1){
obstacleGrid[0][i] = 0;
continue;
}
obstacleGrid[0][i] = obstacleGrid[0][i-1];
}
for(int i = 1;i < m;++i){
for(int j = 1;j < n;++j){
if(obstacleGrid[i][j] == 1){
obstacleGrid[i][j] = 0;
continue;
}
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
}
}
return obstacleGrid[m-1][n-1];
}
}
空間優(yōu)化略
12.最小路徑和（leetccode 64 M.）
給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格烛谊，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小嘉汰。
說(shuō)明：每次只能向下或者向右移動(dòng)一步晒来。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。
分析：
最優(yōu)子結(jié)構(gòu)問(wèn)題優(yōu)先想DP
確定狀態(tài)
定義dp[m] [n] 其中dp[i] [j] 表示從起點(diǎn)到（i郑现，j）的最小路徑
找到狀態(tài)轉(zhuǎn)移方程
顯然（i湃崩，j）必定是由（i-1，j）或者（i接箫，j-1）得到所以只需要找出兩者的最小路徑即可
所以狀態(tài)轉(zhuǎn)移方程為：dp[i] [j] = min(dp[i-1] [j],dp[i] [j-1]) + a[i] [j]
確定初值
邊界上的點(diǎn)只有一種走法并且
dp[i] [0] = dp[i-1] [0] + a[i] [0]
dp[0] [j] = dp[0] [j-1] + a[0] [j]
代碼：
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i = 1;i < m;++i){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i = 1;i < n;++i){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i = 1;i < m;++i){
for(int j = 1;j < n;++j){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
空間優(yōu)化略
