算法第三章上机实践报告

第一题：

题目描述：

 

算法描述：

很显然这道题我们要用动态规划来做。我们需要动态的求出每个往下走能的得到的最大的和。

我们用一个dp【】数组来记录每个位置上能取到的最大的和，数组a【】为这个位置上本身的值。

很显然，从顶点开始（设顶点为1）我们比较与它相连的两个点（设为2，3）的dp【2】，dp【3】取较大那个然后加上它本身a【1】就是答案。

然后用递归的思想，dp【2】就是它的dp【4】，dp【5】中较大的加上它本身。

一直到最后一行的dp【】就是它自己本身a【】。

即状态转移方程为  dp【i】【j】=a【i】【j】+max（dp【i+1，j】，dp【i+1，j+1】）

AC代码：

 1 #include <iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,a[101][101],dp[101][101];
 5 int DP(int i,int j){
 6 if(dp[i][j]>0) return dp[i][j];//代码优化，已经计算过的直接返回避免重复计算，降低复杂度
 7 return dp[i][j]=a[i][j]+((i==n)?0:max(DP(i+1,j),DP(i+1,j+1)));
 8 }
 9 int main() {
10 cin>>n;
11 for (int i = 1; i <=n; i++)
12 for(int j=1;j<=i;j++)
13 cin>>a[i][j];
14 cout<<DP(1,1)<<'\n';
15 return 0;
16 }

View Code

复杂度分析：

因为我代码本身已经优化了，不会重复计算已经算过的dp【】【】值，所以算法时间复杂度为 O（n^2）;

二维数组dp【】【】保存每个子问题的解，空间复杂度为O（n^2)

心得体会：

复习了动态规划算法，加强了对动态规划算法的理解和认识，并且上机实践加强了敲代码的能力。