問題描述
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 Start ）。
機器人每次只能向下或者向右移動一步匾效。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 Finish ）舷蟀。
問總共有多少條不同的路徑？
示例
輸入：m = 3, n = 7
輸出：28
輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始面哼，總共有 3 條路徑可以到達右下角野宜。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
解題思路
如圖，我們可以看出第一行和第一列因為規(guī)則限制（只能向下或者向右移動一步）魔策，可以直接得到路徑數(shù)匈子；而到達C點的走法可以由相鄰的A、B點得出闯袒；也就是說虎敦，到達網(wǎng)格每一塊的不同路徑數(shù)都可以由相鄰的節(jié)點進行推導。
由此政敢，我們可以這么來解決這個問題：
a. 定義數(shù)組儲存中間狀態(tài)：dp[i][j]
b. 找到遞推公式（狀態(tài)轉移方程或者DP方程）：
dp[i][j] = dp[i - 1][j] + dp[i[j - 1](相鄰不為空地)
代碼示例（JAVA）
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
時間復雜度：O(m*n)
問題描述
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為 Start ）其徙。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為 Finish）喷户。
現(xiàn)在考慮網(wǎng)格中有障礙物唾那。那么從左上角到右下角將會有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示褪尝。
示例
解題思路
這道題在62. 不同路徑的基礎上加了一些限制條件闹获，遇到障礙不計算即可期犬；同時要注意的是，我們可以用一維數(shù)組存儲中間狀態(tài)避诽，節(jié)約空間龟虎；另外，要注意起點就是障礙物的情況茎用。
代碼示例（JAVA）
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
return 0;
}
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 (i == 0 && j == 0) {
dp[j] = 1;
} else if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] += (j >= 1 ? dp[j - 1] : 0);
}
}
}
return dp[n - 1];
}
}
時間復雜度：O(m*n)
問題描述
給定兩個字符串 text1 和 text2遣总，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 轨功，返回 0 旭斥。
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如古涧，ace 是 abcde 的子序列垂券，但 aec 不是 abcde 的子序列。
兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列羡滑。
示例
輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：最長公共子序列是 "ace" 菇爪，它的長度為 3 。
輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc" 柒昏，它的長度為 3 凳宙。
輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個字符串沒有公共子序列，返回 0 职祷。
解題思路
思路：找到規(guī)律氏涩，轉換為動態(tài)規(guī)劃問題，找到DP方程
用二維數(shù)組去遞推兩個字符串的
公共子序列情況：當
text1[i]=text2[j] 時有梆，將這兩個相同的字符稱為公共字符是尖；如果用dp[i-1][j-1]表示text1[0~i-1]和text2[0~j-1]的公共子序列，那么dp[i][j]就是 dp[i-1][j-1]加上這個公共字符泥耀；當不相同時饺汹，
dp[i][j] = Max(dp[i-1][j], dp[i][j-1])
代碼示例（JAVA）
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
char char1 = text1.charAt(i);
for (int j = 0; j < n; j++) {
char char2 = text2.charAt(j);
if (char1 == char2) {
dp[i][j] = (i >= 1 && j >= 1 ? dp[i - 1][j - 1] : 0) + 1;
} else {
dp[i][j] = Math.max(i >= 1 ? dp[i - 1][j] : 0, j >= 1 ? dp[i][j - 1] : 0);
}
}
}
return dp[m - 1][n - 1];
}
}
時間復雜度：O(m*n)
問題描述
給定一個三角形 triangle ，找出自頂向下的最小路徑和痰催。
每一步只能移動到下一行中相鄰的結點上兜辞。相鄰的結點 在這里指的是 下標 與 上一層結點下標 相同或者等于 上一層結點下標 + 1 的兩個結點。也就是說陨囊，如果正位于當前行的下標 i 弦疮，那么下一步可以移動到下一行的下標 i 或 i + 1 。
示例
輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：如下面簡圖所示：
2
3 4
6 5 7
4 1 8 3
自頂向下的最小路徑和為 11（即蜘醋，2 + 3 + 5 + 1 = 11）胁塞。
解題思路
顯而易見的動態(tài)規(guī)劃題，自底向上遞推即可啸罢。
代碼示例（JAVA）
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int m = triangle.size();
int[] dp = triangle.get(m - 1).stream()
.mapToInt(Integer::intValue)
.toArray();
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
}
時間復雜度：O(n*n)
問題描述
給你一個整數(shù)數(shù)組 nums 编检，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和扰才。
子數(shù)組 是數(shù)組中的一個連續(xù)部分允懂。
示例
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 衩匣。
解題思路
A.找到重復性子問題：找到以數(shù)組中每個數(shù)字結尾的最大和蕾总。
B.存儲中間狀態(tài)：dp[i]
C.找到DP方程：
分類討論，如果nums[i]>0琅捏，dp[i] = dp[i-1] + nums[i]生百；如果nums[i]<=0，dp[i] = dp[i-1]柄延；
綜上所述蚀浆，合并可能出現(xiàn)的情況，dp[i] = Math.max(dp[i-1] + nums[i], dp[i-1])
要注意的是：在每一輪中搜吧，只會用到前一個也就是dp[i-1]市俊，可以對此做空間上的優(yōu)化。
代碼示例（JAVA）
class Solution {
public int maxSubArray(int[] nums) {
int pre = nums[0], max = nums[0];
for (int i = 1; i < nums.length; i++) {
pre = Math.max(pre + nums[i], nums[i]);
max = Math.max(pre, max);
}
return max;
}
}
時間復雜度：O(n)
問題描述
給你一個整數(shù)數(shù)組 nums 滤奈，請你找出數(shù)組中乘積最大的非空連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字）摆昧，并返回該子數(shù)組所對應的乘積。
測試用例的答案是一個 32-位 整數(shù)蜒程。
子數(shù)組 是數(shù)組的連續(xù)子序列据忘。
示例
輸入: nums = [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6。
輸入: nums = [-2,0,-1]
輸出: 0
解釋: 結果不能為 2, 因為 [-2,-1] 不是子數(shù)組搞糕。
解題思路
這道題與53. 最大子數(shù)組和相似，但是不同的是：可能出現(xiàn)負負得正的情況曼追，并不能簡單的由前者的最大乘積推導出后者的最大乘積窍仰，前者的最小乘積可能由于當前的負數(shù)變成最大。
代碼示例（JAVA）
class Solution {
public int maxProduct(int[] nums) {
int max = nums[0];
int[] dpMax = new int[nums.length];
int[] dpMin = new int[nums.length];
dpMax[0] = dpMin[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(dpMin[i - 1] * nums[i], nums[i]));
dpMin[i] = Math.min(dpMax[i - 1] * nums[i], Math.min(dpMin[i - 1] * nums[i], nums[i]));
max = Math.max(max, dpMax[i]);
}
return max;
}
}
時間復雜度：O(n)
問題描述
給你一個整數(shù)數(shù)組 coins 礼殊，表示不同面額的硬幣驹吮；以及一個整數(shù) amount ，表示總金額晶伦。
計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 碟狞。如果沒有任何一種硬幣組合能組成總金額，返回 -1 婚陪。
你可以認為每種硬幣的數(shù)量是無限的族沃。
示例
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
輸入：coins = [2], amount = 3
輸出：-1
輸入：coins = [1], amount = 0
輸出：0
解題思路
A. 找到重復性子問題：
如果想表示12所需的最少的硬幣個數(shù)，那么可以由當前硬幣組推出1+11、2+10脆淹、5+6三種組合方式常空；然后繼續(xù)往下找11、10盖溺、6的最少組合方式...
B.存儲中間狀態(tài)：dp[i]表示組成總金額i需要的硬幣個數(shù)昙沦；
C.找到DP方程：
dp[i] = Min(dp[i - 1], dp[i - 2], dp[i - 5]) + 1
其中在岂，1、2、5為硬幣組衔蹲；
另外，如果dp[i - 1]吼旧、dp[i - 2]背苦、dp[i - 5]都不存在，dp[i] = -1
代碼示例（JAVA）
class Solution {
int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
int[] dp = new int[amount + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int min = Integer.MAX_VALUE;
for (int coin : coins) {
if (coin <= i && dp[i - coin] >= 0) {
int res = dp[i - coin] + 1;
min = Math.min(min, res);
}
}
dp[i] = (min == Integer.MAX_VALUE) ? -1 : min;
}
return dp[amount];
}
}
時間復雜度：O(m*n)
問題描述
你是一個專業(yè)的小偷遗契，計劃偷竊沿街的房屋辐棒。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)牍蜂，如果兩間相鄰的房屋在同一晚上被小偷闖入漾根，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組鲫竞，計算你 不觸動警報裝置的情況下 辐怕，一夜之內(nèi)能夠偷竊到的最高金額。
示例
輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) 从绘，然后偷竊 3 號房屋 (金額 = 3)寄疏。
偷竊到的最高金額 = 1 + 3 = 4 。
輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)僵井，接著偷竊 5 號房屋 (金額 = 1)陕截。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。
解題思路
A. 找到重復性子問題：
偷竊到第n個房屋獲得的最高金額批什，需要前幾個房屋的偷竊情況农曲；前面幾個房屋的偷竊情況，需要更前面的房屋進行推導......
B.存儲中間狀態(tài)：dp[i][2]
dp[i]表示到達第i個房屋的情況驻债，dp[i][0]表示偷竊了第i個房屋乳规，dp[i][1]表示沒偷竊第i個房屋。
C.找到DP方程：
dp[i][0] = nums[i] + dp[i - 1][1]
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1])
注：如果第i個房屋不偷合呐，那么當前的最高金額應該從上一個房屋的兩種情況中取最高值暮的。
代碼示例（JAVA）
class Solution {
public int rob(int[] nums) {
int length = nums.length;
// 二位數(shù)組，第一位表示偷當前房屋淌实；第二位表示不偷當前房屋
int[][] dp = new int[length][2];
dp[0] = new int[]{nums[0], 0};
for (int i = 1; i < length; i++) {
// 偷
dp[i][0] = nums[i] + dp[i - 1][1];
// 不偷
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
return Math.max(dp[length - 1][0], dp[length - 1][1]);
}
}
時間復雜度：O(n)
