对动态规划算法的理解

时间:2022-03-29 18:44:43

一、对动态规划的理解

  动态规划思想与分治法类似,都是将问题分解为多个子问题,通过求解子问题来得到最终答案,而动态规划的优势在于,动态规划防止了子问题的重复计算,每个问题只计算一次,自底向上地求出原问题的解。

二、编程题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]

三、结队编程情况

  本次编程我们先各自独立编程,编程完成或是遇见困难后,再交流各自的思路并尝试优化对方的算法。总体来看,我们的思路基本一致,算法的时间复杂度一致,但空间复杂度略有差别,通过讨论后,我们认为两种方法都可行,一种更加通用,一种趋向于实际问题的求解,因而我们决定各自保留自己的算法,不做统一