动态规划无后效性

时间：2014-10-26 10:14:46 阅读：162 评论：0 收藏：0 [点我收藏+]

无后效性是动态规划的重要标记，

概念：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响，简单的说，就是“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段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

动态规划无后效性

原文：http://www.cnblogs.com/shenyanqi/p/4051400.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)