算法第3章实践报告

• 实践题目名称

• 问题描述

该问题是：给一段序列，求怎么取一小段，使得相加所得的和数最大，也即最大子段和问题。

• 算法描述

  初始化dp数组，定义dp数组dp[i]为从1到 i 中最大的子段和。

 动态规划转移方程，明显可以知道：dp[ i ] = max( dp[ i-1 ] , k ) ; k 为从 0 到 i 的相加的和大于0的子段，一旦小于0就从当前位置重新计段长。

　　　　模拟过程如下：

代码实现

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,temp[10005],dp[10005],flag = 0,k;
 4 int main()
 5 {
 6     /* input */
 7     cin>>n;
 8     for(int i = 1;i<=n;i++)
 9     {
10         cin>>temp[i];
11         if(temp[i] >=0) flag = 1;
12     }
13 
14     /*    dp[i]:1-i中最大子段和
15         k: k从0到i加和大于0的子段，遇到子段小于0的扔掉重新开始计长度*/
16     for(int i = 1;i<=n;i++)
17     {
18         if(k>0) k += temp[i];
19         else k=temp[i];        
20         dp[i] = max(dp[i-1], k);
21     }
22     
23     /* answer */ 
24     if(flag == 0) cout<<0;
25     else cout<<dp[n];
26     return 0;
27 }

• 算法时间及空间复杂度分析（要有分析过程）

算法时间复杂度分析：

因为使用了一个for循环，

所以时间复杂度T(n)=O(n)

算法空间复杂度分析：

用了辅助空间一维数组dp[n]，

所以空间复杂度为O(n)

• 心得体会（对本次实践收获及疑惑进行总结）

经过第一次实践合作之后，第二次的实践合作愈发顺利，但可能是我们看视频理解得不够深入，在写递推式的时候，还是会卡顿，而且没有理解好一些定义，使得最后虽然编程过滤，但是在回答老师问题的时候还是会回答不出来。

• 动态规划的个人体会和思考

 ===动态规划问题的特点：

（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

（2）重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

===动规解题的一般思路：

　　动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。

　　动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

　　　　初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

　 （1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。    

　 （2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。    

　 （3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。    

　 （4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。