阿里巴巴做短视频网站,兰州网站设计,wordpress 4.4.8,谷歌广告投放教程#x1f447;woc#xff0c;这不是最熟悉那种#xff0c;记忆化 dfs 或者 普通的深度优先搜索#xff1f;#xff1f;都适用于二维地图#x1f447;
DFS#xff08;深度优先搜索#xff09;8种题型_dfs典型问题-CSDN博客 目录
#x1f943;不同路径
#x1f33c;最…woc这不是最熟悉那种记忆化 dfs 或者 普通的深度优先搜索都适用于二维地图
DFS深度优先搜索8种题型_dfs典型问题-CSDN博客 目录
不同路径
最小路径和
最长回文子串
AC 中心扩散
AC 动态规划
最长公共子序列
编辑距离 不同路径
62. 不同路径 - 力扣LeetCode “只能向下 或 向右”注意限制条件 注意二维vector的初始化也可以直接用数组 /*
dp[i][j] : 到达(i, j)的路径数
dp[i][j] dp[i - 1][j] dp[i][j - 1] 每个点只来自于上边和左边
初始化 : dp[i][0] 1, dp[][j] 1
*/
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 0)); // m行, 每一行 n 个元素for (int j 0; j n; j) dp[0][j] 1; // 第一行初始化for (int i 0; i m; i)dp[i][0] 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];}
};
最小路径和
64. 最小路径和 - 力扣LeetCode “只能向下 或 向右”注意限制条件 和上一题初始化不同上一条是不同路径本题是最小路径和 /*
dp[i][j] : 到达(i, j)的最小路径和
dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]
初始化 : dp[0][0], 然后从 (0,0) 开始分别向右向下初始化第 0 行第 0 列
*/
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dp(m, vectorint(n, 0));dp[0][0] grid[0][0];for (int j 1; j n; j)dp[0][j] dp[0][j - 1] grid[0][j]; // 第 0 行for (int i 1; i m; i)dp[i][0] dp[i - 1][0] grid[i][0]; // 第 0 列for (int i 1; i m; i)for (int j 1; j n; j) {dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];}return dp[m-1][n-1];}
};
最长回文子串
5. 最长回文子串 - 力扣LeetCode
AC 中心扩散 遍历每一个字母以这个字母为中心往外扩散先找到以此为中心全部相同的字母 比如 acdbbd 中的 bb然后同时开始左右扩散l - 1, r 1直到遇到左右边界不相等的字母d d后面就不相等了所以最长回文子串是 dbbd 时间 O(n^2)
class Solution {
public:string longestPalindrome(string s) {int l 0, r 0, maxLen 1; // 初始化 l, r 防止一个元素 out of rangefor (int i 0; i s.size(); i) {int left i - 1, right i 1, len 1; // len 当前长度// 左边 s[i] 的while (left 0 s[left] s[i]) {left--;len; }// 右边 s[i] 的while (right s.size() s[right] s[i]) {right;len;}// 左右同时扩展while (left 0 right s.size() s[left] s[right]) left--, right, len 2;if (len maxLen) {maxLen len;l left 1, r right - 1; // 最长子串区间 [l, r]}}return s.substr(l, r - l 1);}
};
AC 动态规划 中心扩散会有大量重复计算比如 abbacd第一个 b 已经计算过的回文串第二个 b 还会重新计算而 dp 能将计算过的状态记住个别情况接近 O(n) 代码写完后貌似没有发现时间上的优化似乎都是差不多的 时间 O(n^2)
/*
dp[i][j] : 子串 [i, j] 区间是否回文
dp[i][j] (dp[i1][j-1] || j - i 1) (s[i] s[j])
初始化 : dp[i][i] 1
*/
class Solution {
public:string longestPalindrome(string s) {int maxLen 1, l 0, r 0, n s.size();// 记得初始化 vector, 正确分配内存, 不然报错 null pointervectorvectorint dp(n, vectorint(n, 0));for (int i 0; i n; i)dp[i][i] 1;for (int j 1; j n; j) // 右边界 jfor (int i 0; i j; i) // 左边界 iif (s[i] s[j] (dp[i 1][j - 1] || j - i 1)) {dp[i][j] 1;if (j - i 1 maxLen)maxLen j - i 1, l i, r j;}return s.substr(l, r - l 1);}
};
最长公共子序列
1143. 最长公共子序列 - 力扣LeetCode dp[][] 下标从 1 开始就不用初始化那么麻烦也就是 dp[1][1] 1表示 text1[0] text2[0] /*
dp[i][j] : s1的[0, i-1] 和 s2的[0, j-1] 的最长公共子序列
if (s1[i-1] s2[j-1]) dp[i][j] dp[i-1][j-1] 1
else dp[i][j] max(dp[i - 1][j], dp[i][j - 1])
初始化 : dp[0][0] 0 OR 1
*/
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m text1.size(), n text2.size();vectorvectorint dp(m1, vectorint(n1, 0));for (int i 1; i m; i) // dp[][] 下标从 1 开始for (int j 1; j n; j) {if (text1[i-1] text2[j-1])dp[i][j] dp[i-1][j-1] 1;elsedp[i][j] max(dp[i-1][j], dp[i][j-1]);}return dp[m][n];}
};// a c b q d b b q
// a c d q
编辑距离
72. 编辑距离 - 力扣LeetCode 1类似上一题dp[][] 下标从 1 开始避免了麻烦的初始化因为递推式有 [i-1][j-1], [i][j-1], [i-1][j] 三种组合下标改 1 开始后 m n 2增删改的递推式中1不一定正确所以要取 增 删 改 的最小值 3初始化观察递推式都是根据 左上左上 三个方位得到的所以初始化第一行和第一列 /*
dp[i][j] : s1 前 i 个字符 -- s2 前 j 个字符下标 1 开始递推式: dp[i][j] ...
取增删改三者的最小值作为新的 dp[i][j]s1 增加1个变 s2: dp[i][j-1] 1
s1 删除1个变 s2: dp[i-1][j] 1
s1 替换1个变 s2: dp[i-1][j-1] 1if (s1[i] s2[j]) dp[i-1][j-1]
*/
class Solution {
public:int minDistance(string word1, string word2) {int m word1.size(), n word2.size();vectorvectorint dp(m1, vectorint(n1, 0));// 初始化for (int i 1; i m; i)dp[i][0] i; // 第一列for (int j 1; j n; j)dp[0][j] j; // 第一行for (int i 1; i m; i)for (int j 1; j n; j) {if (word1[i-1] word2[j-1])dp[i][j] dp[i - 1][j - 1]; // 不用操作else // 增删改的最小值dp[i][j] min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) 1;}return dp[m][n];}
};
