1. 题⽬链接:300.最⻓递增⼦序列
2. 题⽬描述:
3. 解法(暴搜->记忆化搜索->动态规划):
算法思路:
暴搜:
a. 递归含义:给dfs ⼀个使命,给他⼀个数i ,返回以i 位置为起点的最⻓递增⼦序列的⻓ 度;
b. 函数体:遍历i 后⾯的所有位置,看看谁能加到i 这个元素的后⾯。统计所有情况下的最⼤ 值。
c. 递归出⼝:因为我们是判断之后再进⼊递归的,因此没有出⼝~
记忆化搜索:
a. 加上⼀个备忘录;
b. 每次进⼊递归的时候,去备忘录⾥⾯看看;
c. 每次返回的时候,将结果加⼊到备忘录⾥⾯。
动态规划:
a. 递归含义->状态表⽰;
b. 函数体->状态转移⽅程;
c. 递归出⼝->初始化。
C++算法代码:
class Solution
{
public:
int lengthOfLIS(vector<int>& nums)
{
// 动态规划
vector<int>dp(nums.size(), 1); //记录每个位置之后的最长递增子序列
int max_size = 0; //最大递增子序列长度
for (int i = nums.size() - 1; i < nums.size(); i--)
{
//计算该位置之后的最长子序列长度
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[j] > nums[i])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
//最大递增子序列长度
max_size = max(max_size, dp[i]);
}
return max_size;
// 记忆化搜索
//
// 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;
}
}
标签:nums,int,max,递增,pos,ret,算法,序列,memo
From: https://blog.csdn.net/2301_79580018/article/details/141160656