Maximum Subarray
DP 问题 全称 (Dynamic Programming)
建议直接读这篇文章, 真的很不错, 虽然是英文, 但是全部都是简单词汇, 只有几个专业术语, 查一下就行了, 不推荐谷歌翻译, 因为我看了下, 有些地方还是自己理解比较好, 谷歌翻译有错误
以上文献是对于 DP 问题的详解
这里列出求解 DP 问题的关键七步 (均由原博文给出)
- How to recognize a DP problem
- Identify problem variables
- Clearly express the recurrence relation
- Identify the base cases
- Decide if you want to implement it iteratively or recursively
- Add memoization
- Determine time complexity
对于第一步, 怎么识别出一个问题是否是 DP 问题, 我们首先要去判断, 我们面对的问题是否可以进行子问题的划分 (这里很多人看到子问题很自然的就想到了递归, 确实原文说了, 但是单纯的递归效率很低, 需要利用已经找到的信息递归就很快), 就比如这道题, 我们要找一个序列中最大的子序列, 并且输出求和.
那么就可以将其看作, 有一个空值, 然后依次把数组的值放进来加, 再比较留最大的, 这样不断一个个加入的过程, 我们就可以将其视作一个个的小的子问题.(原博文作者把第一步是看作最重要的一步)
其他步骤, 我觉得还是原文讲的更为清楚, 就不在这里献丑.
总结就是, 再从子问题中找到关键变量, 然后再找到子问题和主问题之间的复现关系, 再决定你是使用非递归或者是递归, 最后就是加入记忆复现数据集 (可以是数组, 也可以是其他的形式, 反正存储你已找到的信息), 再编写.
那么这道题解决方式就是呼之欲出, 并且按照这个思想代码理解更为容易.
- class Solution {
- public:
- int MaxSubarray(vector<int> &nums) {
- if (nums.size() == 0) return 0;
- if (nums.size() == 1)return nums.at(0);// 前两步都是简单的检查, 如果容器内没有元素或是只有一个那么就返回 0 或者是返回其本身
- int Memory_Max = nums.at(0);// 记忆最大值
- int Real_Max = nums.at(0);// 在当前步骤中的最大值, 这也是子问题与主问题产生联系的地方
- size_t nums_length = nums.size();
- for (size_t i = 1; i != nums_length; i++) {
- Memory_Max = std::max(Memory_Max + nums.at(i), nums.at(i));// 这一步就是将记忆的最大值与后面的值相加, 再与其比较, 也就是不断添加的过程, 将当前的已加入的数据序列的最大序列的值记忆.
- // 其实这个思想很想迪杰斯特拉寻找最短路径的问题 (没学过数据结构的朋友可以把这里忽略)
- // 不断把最短路径找出, 并且在寻找过程中不断的更新最短路径的节点
- Real_Max = std::max(Memory_Max, Real_Max);// 与当前真实最大值进行比较
- }
- return Real_Max;
- }
- };
来源: http://www.bubuko.com/infodetail-3365720.html