【综合算法学习】（第十九篇）
目录
不同路径（medium）
题目解析
讲解算法原理
编写代码
最⻓递增⼦序列（medium）
题目解析
讲解算法原理
编写代码
不同路径（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
⼀个机器⼈位于⼀个mxn⽹格的左上⻆（起始点在下图中标记为“Start”）。机器⼈每次只能向下或者向右移动⼀步。机器⼈试图达到⽹格的右下⻆（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
⽰例1：
输⼊：m=3,n=7
输出：28
⽰例2：
输⼊：m=3,n=2
输出：3
解释：
从左上⻆开始，总共有3条路径可以到达右下⻆。
1.向右->向下->向下
2.向下->向下->向右
3.向下->向右->向下
讲解算法原理
解法（暴搜->记忆化搜索->动态规划）：
算法思路：
暴搜：
a. 递归含义：给 dfs ⼀个使命，给他⼀个下标，返回从 [0, 0] 位置⾛到 [i, j] 位置⼀
共有多少种⽅法；
b. 函数体：只要知道到达上⾯位置的⽅法数以及到达左边位置的⽅法数，然后累加起来即可；c. 递归出⼝：当下标越界的时候返回 0 ；当位于起点的时候，返回 1 。
记忆化搜索：
a. 加上⼀个备忘录；
b. 每次进⼊递归的时候，去备忘录⾥⾯看看；
c. 每次返回的时候，将结果加⼊到备忘录⾥⾯。
动态规划：
a. 递归含义->状态表⽰；
b. 函数体->状态转移⽅程；
c. 递归出⼝->初始化。
编写代码
c++算法代码：
class Solution
{
public:
int uniquePaths(int m, int n)
{
// 动态规划
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[1][1] = 1;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
if(i == 1 && j == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
return dp[m][n];
// 记忆化搜索
// vector<vector<int>> memo(m + 1, vector<int>(n + 1));
// return dfs(m, n, memo);
}
int dfs(int i, int j, vector<vector<int>>& memo)
{
if(memo[i][j] != 0)
{
return memo[i][j];
}
if(i == 0 || j == 0) return 0;
if(i == 1 && j == 1)
{
memo[i][j] = 1;
return 1;
}
memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
return memo[i][j];
}
};java算法代码：
class Solution
{
public int uniquePaths(int m, int n)
{
// 动态规划
int[][] dp = new int[m + 1][n + 1];
dp[1][1] = 1;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
if(i == 1 && j == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
return dp[m][n];
// 记忆化搜索
// int[][] memo = new int[m + 1][n + 1];
// return dfs(m, n, memo);
}
public int dfs(int i, int j, int[][] memo)
{
if(memo[i][j] != 0)
{
return memo[i][j];
}
if(i == 0 || j == 0) return 0;
if(i == 1 && j == 1)
{
memo[i][j] = 1;
return 1;
}
memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
return memo[i][j];
}
}最⻓递增⼦序列（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums，找到其中最⻓严格递增⼦序列的⻓度。⼦序列是由数组派⽣⽽来的序列，删除（或不删除）数组中的元素⽽不改变其余元素的顺序。例
如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的⼦序列。
⽰例1：
输⼊：nums=[10,9,2,5,3,7,101,18]
输出：4
解释：最⻓递增⼦序列是[2,3,7,101]，因此⻓度为4。
⽰例2：
输⼊：nums=[0,1,0,3,2,3]
输出：4
⽰例3：
输⼊：nums=[7,7,7,7,7,7,7]
输出：1
提⽰：
1<=nums.length<=2500
-10^4<=nums[i]<=10^4
讲解算法原理
解法（暴搜->记忆化搜索->动态规划）：
算法思路：
暴搜：
a. 递归含义：给 dfs ⼀个使命，给他⼀个数 i ，返回以 i 位置为起点的最⻓递增⼦序列的⻓
度；
b. 函数体：遍历 i 后⾯的所有位置，看看谁能加到 i 这个元素的后⾯。统计所有情况下的最⼤
值。
c. 递归出⼝：因为我们是判断之后再进⼊递归的，因此没有出⼝~
记忆化搜索：
a. 加上⼀个备忘录；
b. 每次进⼊递归的时候，去备忘录⾥⾯看看；
c. 每次返回的时候，将结果加⼊到备忘录⾥⾯。
动态规划：
a. 递归含义->状态表⽰；
b. 函数体->状态转移⽅程；
c. 递归出⼝->初始化。
编写代码
c++算法代码：
class Solution
{
public:
int lengthOfLIS(vector<int>& nums)
{
// 动态规划
int n = nums.size();
vector<int> dp(n, 1);
int ret = 0;
// 填表顺序：从后往前
for(int i = n - 1; i >= 0; i--)
{
for(int j = i + 1; j < n; j++)
{
if(nums[j] > nums[i])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
ret = max(ret, dp[i]);
}
return ret;
// 记忆化搜索
//
// vector<int> memo(n);
// int ret = 0;
// for(int i = 0; i < n; i++)
// ret = max(ret, dfs(i, nums, memo));
// return ret;
}
int dfs(int pos, vector<int>& nums, vector<int>& memo)
{
if(memo[pos] != 0) return memo[pos];
int ret = 1;
for(int i = pos + 1; i < nums.size(); i++)
{
if(nums[i] > nums[pos])
{
ret = max(ret, dfs(i, nums, memo) + 1);
}
}
memo[pos] = ret;
return ret;
}
};java算法代码：
class Solution
{
public int lengthOfLIS(int[] nums)
{
int n = nums.length;
int[] dp = new int[n];
int ret = 0;
Arrays.fill(dp, 1);
// 填表顺序: 从后往前
for(int i = n - 1; i >= 0; i--)
{
for(int j = i + 1; j < n; j++)
{
if(nums[j] > nums[i])
{
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
// 记忆化搜索
// int ret = 0;
// int n = nums.length;
// int[] memo = new int[n];
// for(int i = 0; i < n; i++)
// {
// ret = Math.max(ret, dfs(i, nums, memo));
// }
// return ret;
}
public int dfs(int pos, int[] nums, int[] memo)
{
if(memo[pos] != 0) return memo[pos];
int ret = 1;
for(int i = pos + 1; i < nums.length; i++)
{
if(nums[i] > nums[pos])
{
ret = Math.max(ret, dfs(i, nums, memo) + 1);
}
}
memo[pos] = ret;
return ret;
}
}