今日任务
62.不同路径
- 题目链接： https://leetcode.cn/problems/unique-paths/description/
- 题目描述：
Code
class Solution {
public:int uniquePaths(int m, int n) {// vector<vector<int>> memo(m, vector<int>(n, -1));// function<int(int, int)> dfs = [&](int i, int j) ->int {// if(i < 0 || j < 0){// return 0;// }// if(i == 0 && j == 0){// return 1;// }// int &res = memo[i][j];// if(res != -1){// return res;// }// return res = dfs(i - 1, j) + dfs(i, j - 1);// };// return dfs(m - 1, n - 1);// vector<vector<int>> dp(m, vector<int>(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];vector<int> dp(n, 1);for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[j] += dp[j - 1];}}return dp[n - 1];}
};
63. 不同路径 II
- 题目链接： https://leetcode.cn/problems/unique-paths-ii/description/
- 题目描述：
Code
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {// 记忆化搜索// int m = obstacleGrid.size(), n = obstacleGrid[0].size();// vector<vector<int>> memo(m, vector<int>(n, -1));// function<int(int, int)> dfs = [&](int i, int j)->int{// if(i < 0 || j < 0 || obstacleGrid[i][j]){// return 0;// }// if(i == 0 && j == 0){// return 1;// }// int &res = memo[i][j];// if(res != -1){// return res;// }// return res = dfs(i - 1, j) + dfs(i, j - 1);// };// return dfs(m - 1, n - 1);// 二维递推// int m = obstacleGrid.size(), n = obstacleGrid[0].size();// vector<vector<int>> dp(m, vector<int>(n));// for(int k = 0; k < m; k++){// if(obstacleGrid[k][0]){// break;// }// dp[k][0] = 1;// }// for(int k = 0; k < n; k++){// if(obstacleGrid[0][k]){// break;// }// dp[0][k] = 1;// }// for(int i = 1; i < m; i++){// for(int j = 1; j < n; j++){// if(obstacleGrid[i][j]){// dp[i][j] = 0;// }else{// dp[i][j] = dp[i - 1][j] + dp[i][j - 1];// }// }// }// return dp[m - 1][n - 1];// 一维递推int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<int> dp(n);dp[0] = 1;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(obstacleGrid[i][j]){dp[j] = 0;}else if(j > 0){dp[j] += dp[j - 1];}}}return dp[n - 1];}
};
343.整数拆分
- 题目链接： https://leetcode.cn/problems/integer-break/description/
- 题目描述：
Code
class Solution {
public:int integerBreak(int n) {// 记忆化搜索vector<int> memo(n + 1, -1);function<int(int)> dfs = [&](int i)->int{if(i == 2){return 1;}int &res = memo[i];if(res != -1){return res;}for(int j = 1; j <= i / 2; j++){res = max(res, max(j * (i - j), j * dfs(i - j)));}return res;};return dfs(n);// 递推// vector<int> dp(n + 1);// dp[2] = 1;// for(int i = 3; i <= n; i++){// for(int j = 1; j <= i / 2; j++){// dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));// }// }// return dp[n];}
};
96.不同的二叉搜索树
- 题目链接： https://leetcode.cn/problems/unique-binary-search-trees/description/
- 题目描述：
Code
class Solution {
public:int numTrees(int n) {// 记忆化搜索// vector<int> memo(n + 1, -1);// function<int(int)> dfs = [&](int i)->int{// if(i == 0 || i == 1){// return 1;// }// int &res = memo[i];// if(res != -1){// return res;// }// res = 0;// for(int j = 0; j < i; j++){// res += dfs(j) * dfs(i - j - 1);// }// return res;// };// return dfs(n);// 递推vector<int> dp(n + 1);dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){for(int j = 0; j < i; j++){dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}
};
