04.05_单序列问题
单序列问题
问题描述
单序列动态规划是指在一个序列上进行状态转移的问题。
常见的有最长上升子序列、最大子数组和等。
通常需要定义状态表示序列中某个位置的最优解。
最长上升子序列(LIS)
算法思想
- 定义dp[i]表示以nums[i]结尾的最长上升子序列长度
- 对于每个位置i，考虑之前所有小于nums[i]的数
- 状态转移方程：dp[i] = max(dp[j] + 1) 其中j < i且nums[j] < nums[i]
- 最终答案为dp数组中的最大值
代码实现
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // 初始化为1
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1); // 初始化为1
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxLen = 0;
for (int len : dp) {
maxLen = Math.max(maxLen, len);
}
return maxLen;
}
def lengthOfLIS(nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n # 初始化为1
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
最大子数组和
算法思想
- 定义dp[i]表示以nums[i]结尾的最大子数组和
- 对于每个位置i，可以选择加入前面的子数组或重新开始
- 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
- 最终答案为dp数组中的最大值
代码实现
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i-1] + nums[i], nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
def maxSubArray(nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
max_sum = dp[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + nums[i], nums[i])
max_sum = max(max_sum, dp[i])
return max_sum
时间复杂度分析
| 最长上升子序列 | ||
| 最大子数组和 |
应用场景
- 最长递增子序列
- 最大子数组和
- 打家劫舍问题
- 股票买卖问题
- 跳跃游戏
注意事项
- 状态定义的选择
- 初始状态的设置
- 状态转移方程的推导
- 空间优化的可能性
- 边界条件的处理
阿里巴巴灵犀互娱公司福利 228人发布