一、对动态规划的理解
动态规划思想与分治法类似,都是将问题分解为多个子问题,通过求解子问题来得到最终答案,而动态规划的优势在于,动态规划防止了子问题的重复计算,每个问题只计算一次,自底向上地求出原问题的解。
二、编程题1、2的递归方程
第一题
int max(int *p,int *m,int n){ int max=0;//用于记录最长子序列的大小 for(int i=0;i<n;i++) m[i]=1;//子序列长度初始化为1 for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if((p[i]>p[j])&&(m[i]<m[j]+1)) { m[i]=m[j]+1;//选择最长子序列 } if(m[i]>=max) max=m[i];//记录最大值 } return max; }
m[i]表示以当前位置的值为子序列末位的最长子序列的长度,同时用max筛选出所有长度的最大值
第二题
int cheap(int *p,int *m,int n){ for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { cin>>p[j]; if(i==1) m[j]=p[j];//初始化m[j]的值 else if(m[j]>(p[j]+m[i])) m[j]=p[j]+m[i];//选择最少租金路径 } return m[n];
因为该问题无需分别求出某一层到另一层的最少租金,故仅仅采用一维数组m[i]表示从第一层到第i层的最少租金,降低了空间复杂度,最终解为m[n]
三、结队编程情况
本次编程我们先各自独立编程,编程完成或是遇见困难后,再交流各自的思路并尝试优化对方的算法。总体来看,我们的思路基本一致,算法的时间复杂度一致,但空间复杂度略有差别,通过讨论后,我们认为两种方法都可行,一种更加通用,一种趋向于实际问题的求解,因而我们决定各自保留自己的算法,不做统一