首页 > 代码库 > 动态规划无后效性
动态规划无后效性
无后效性是动态规划的重要标记，
概念：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响，简单的说，就是“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其它状态没有关系，特别是与未发生的状态没有关系。从图论的角度去考虑，如果把这个问题中的状态定义成图中的顶点，两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则构成一个有向无环加权图，因此，这个图可以进行“拓扑排序”，至少可以按它们拓扑排序的顺序去划分阶段。
来源： <http://baike.baidu.com/view/2862466.htm?fr=aladdin>
实例：题：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6
来源： <https://oj.leetcode.com/problems/maximum-subarray/>
自己的代码：
class Solution {
public:
int maxSubArray(int A[], int n) {
int max = INT_MIN;
int num = 0;
int t = 0;
for(int i = 0;i < n;i ++){
num += A[i];
if(A[i] > 0){
if(num < A[i]){num = A[i];}
}
else{
if(A[i] > num) num = A[i];
}
if(max < num) max = num;
}
return max;
}
};
师傅博客：http://ofpsxx.com
动态规划无后效性
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。