问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 Start ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 Finish ）。
问总共有多少条不同的路径？
示例
输入：m = 3, n = 7
输出：28
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
解题思路
如图，我们可以看出第一行和第一列因为规则限制（只能向下或者向右移动一步），可以直接得到路径数；而到达C点的走法可以由相邻的A、B点得出；也就是说，到达网格每一块的不同路径数都可以由相邻的节点进行推导。
由此，我们可以这么来解决这个问题：
a. 定义数组储存中间状态：dp[i][j]
b. 找到递推公式（状态转移方程或者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 网格的左上角 （起始点在下图中标记为 Start ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 Finish）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例
解题思路
这道题在62. 不同路径的基础上加了一些限制条件，遇到障碍不计算即可；同时要注意的是，我们可以用一维数组存储中间状态，节约空间；另外，要注意起点就是障碍物的情况。
代码示例（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 。
解题思路
思路：找到规律，转换为动态规划问题，找到DP方程
用二维数组去递推两个字符串的
公共子序列情况：当
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）。
解题思路
显而易见的动态规划题，自底向上递推即可。
代码示例（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)
问题描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解题思路
A.找到重复性子问题：找到以数组中每个数字结尾的最大和。
B.存储中间状态：dp[i]
C.找到DP方程：
分类讨论，如果nums[i]>0，dp[i] = dp[i-1] + nums[i]；如果nums[i]<=0，dp[i] = dp[i-1]；
综上所述，合并可能出现的情况，dp[i] = Math.max(dp[i-1] + nums[i], dp[i-1])
要注意的是：在每一轮中，只会用到前一个也就是dp[i-1]，可以对此做空间上的优化。
代码示例（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)
问题描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
解题思路
这道题与53. 最大子数组和相似，但是不同的是：可能出现负负得正的情况，并不能简单的由前者的最大乘积推导出后者的最大乘积，前者的最小乘积可能由于当前的负数变成最大。
代码示例（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)
问题描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
输入：coins = [2], amount = 3
输出：-1
输入：coins = [1], amount = 0
输出：0
解题思路
A. 找到重复性子问题：
如果想表示12所需的最少的硬币个数，那么可以由当前硬币组推出1+11、2+10、5+6三种组合方式；然后继续往下找11、10、6的最少组合方式...
B.存储中间状态：dp[i]表示组成总金额i需要的硬币个数；
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)
问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例
输入：[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.存储中间状态：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;
// 二位数组，第一位表示偷当前房屋；第二位表示不偷当前房屋
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)
