分治+回溯+递归+动态规划
1.人肉递归低效、很累
2.找到最近最简方法，将其拆解成可重复解决的问题
3.数学归纳法思维(地址人肉递归的诱惑)
动态规划:Divide & Conquer + Optimal substructure 分治+最优子结构
关键点
动态规划和递归或者分治没有根本上的区别(关键看有无最优的子结构)
共性:找到重复子问题
差异性:最优子结构、中途可以淘汰次优解
斐波那契数列
傻递归
int fib(int n){
if(n==0){
return 0;
}
}
记忆化搜索
//记忆化搜索
public int fib0(int n,int memo[]){
if(n <= 1)return n;
if (memo[n] ==0)
memo[n] = fib0(n-1,memo) + fib0(n-2,memo);
return memo[n];
}
BottomUp
//BottomUp
public int fib1(int n){
if (n <= 1) return n;
int a[] = new int[n+1];
a[0] = 0;
a[1] = 1;
for (int i = 2;i<=n;i++){
a[i] = a[i-1]+a[i-2];
}
return a[n];
}
路径计数
状态转移方程opt[i,j] = opt[i+1,j] + opt[i,j+1]
完整逻辑:
if(a[i,j] = '空地'){
opt[i,j] = opt[i+1,j] + opt[i,j+1]
}else{
opt[i,j] = 0;
}
image.png
动态规划关键点
1.最优子结构opt(n) = bestof(opt[n-1]+opt[n-2]...);
2.储存中间状态:opt[i]
3.递推公式(美其名曰:状态转移方程或DP方程)
Fib:opt[i] = opt[n-1] + opt[n-2];
二维路径:opt[i,j] = opt[i+1][j] + opt[i]j+1
不同路径(Facebook,亚马逊,微软)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
-
向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
image.png
public int uniquePaths(int m, int n) {
int a[][] = new int[m][n];//从(i,j)走到end的不同路径数
for (int i = m-1;i>=0;i--){
for (int j = n-1;j>=0;j--){
if (i == m-1 || j== n-1){
a[i][j] = 1;
}else {
a[i][j] = a[i][j+1] + a[i+1][j];
}
}
}
return a[0][0];
}
public int uniquePaths0(int m,int n){
int a[][] = new int[m][n];//从start走到(i,j)的不同路径数
for (int i = 0;i<m;i++){
for (int j=0;j<n;j++){
if (i == 0||j == 0){
a[i][j] = 1;
}else{
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
}
return a[m-1][n-1];
}
不同路径II(谷歌、美团、微软)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
image.png
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
image.png
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
-
向下 -> 向下 -> 向右 -> 向右
示例 2：
image.png
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
一、题目分析
递归思路：
假设我们定义到达右下角的走法数为 f(m, n)f(m,n), 因为右下角只能由它上方或者左方的格子走过去，因此可以很容易的写出递归求解式，即 f(m, n) = f(m - 1, n) + f(m, n - 1)f(m,n)=f(m−1,n)+f(m,n−1)，最后加上递归终止条件，SO EASY 看起来大功告成啦！
然而事情并木有结束～ 因为这样自底向上的递归会存在大量的重复计算，所以我们将其改写为在二维数组中自顶向下的递推即可，即 dp[i, j] = dp[i - 1, j] + dp[i, j - 1]dp[i,j]=dp[i−1,j]+dp[i,j−1]。
1、状态定义：
dp[i][j]dp[i][j] 表示走到格子 (i, j)(i,j) 的方法数。
2、状态转移：
如果网格 (i, j)(i,j) 上有障碍物，则 dp[i][j]dp[i][j] 值为 00，表示走到该格子的方法数为 00；
否则网格 (i, j)(i,j) 可以从网格 (i - 1, j)(i−1,j) 或者 网格 (i, j - 1)(i,j−1) 走过来，因此走到该格子的方法数为走到网格 (i - 1, j)(i−1,j) 和网格 (i, j - 1)(i,j−1) 的方法数之和，即 dp[i, j] = dp[i - 1, j] + dp[i, j - 1]dp[i,j]=dp[i−1,j]+dp[i,j−1]。
状态转移方程如下：
dp[i][j]=dp[i−1,j]+dp[i,j−1] (i,j)上无障碍物
dp[i][j]=0 (i,j)上有障碍物
3、初始条件
第 1 列的格子只有从其上边格子走过去这一种走法，因此初始化 dp[i][0] 值为 1，存在障碍物时为 0；
第 1 行的格子只有从其左边格子走过去这一种走法，因此初始化 dp[0][j] 值为 1，存在障碍物时为 0。
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0)return 0;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int dp[][] = new int[m][n];
//第一列
for (int i = 0;i<m && obstacleGrid[i][0] == 0;i++){
dp[i][0] = 1;
}
//第一行
for (int j = 0;j<n && obstacleGrid[0][j] == 0;j++){
dp[0][j] = 1;
}
for (int i = 1;i<m;i++)
for (int j= 1;j<n;j++)
if (obstacleGrid[i][j] == 0)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}
最长公共子序列(字节、谷歌、亚马)
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
解题思路
动态规划思想是希望连续的，也就是说上一个状态和下一个状态(自变量)之间有关系而且连续。
子序列不是连续的，两个字符串 s1 = "abcde"，s2 = "ace"，最长公共子序列是 "ace"。
dp[i][j]：表示长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]。
(1) 若当前字符相同，则找到了一个公共元素，并将公共子序列的长度在 f(i - 1)(j - 1) 的基础上再加 1，此时状态转移方程：dp[i][j] = dp[i-1][j-1] + 1。
子序列不一定都是连续的，只要前面有相同的子序列，哪怕当前比较的字符不一样，那么当前字符串之前的子序列也不会为 0。
换句话说，(2) 若当前字符不同，我们只需要把第一个字符串往前退一个字符或者第二个字符串往前退一个字符然后记录最大值即可(相当于看 text1[0, i - 2] 与 text2[0, j - 1] 的最长公共子序列 和 text1[0, i - 1] 与 text2[0, j - 2] 的最长公共子序列，取最大的)，此时状态转移方程：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。
示例：text1 = "abcde"，text2 = "ace"。
因为当前位置的公共子序列的长度只与它上面或左面的公共长度有关，所以边界上的长度均为 1。
当 text1 遍历到 "abc" 且 text2 遍历到 "ac" 时，此时 "c == c"，则 dp[3][2] = dp[2][1] + 1 = 2；
当 text1 遍历到 "abc" 且 text2 遍历到 "ace" 时，此时 "c != e"，则在 "abc 和 ac" 中的最长公共子
序列长度和 "ab 和 ace" 中的最长公共子序列长度中，取最大的：dp[3][3] = dp[3][2] = 2。
因为 "e" 不属于两个字符串中的公共子序列，所以当 text1 遍历到 "c" 且 text2 遍历到 "e" 时的最长
公共子序列应该与在遍历到 "e" 之前就已经找到的最长公共子序列相同，即dp[i - 1][j] 和dp[i][j - 1]
中取较大的值。
image.png
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
if (m == 0|| n == 0) return 0;
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];
}
网友评论