算法第三章作业

时间:2021-06-05 21:58:20
  1. 你对动态规划算法的理解
  2. 分别列出编程题1、2的递归方程
  3. 说明结对编程情况

    1.你对动态规划算法的理解

应用动态规划的算法一般比较复杂且有规律性,这与分治法类似,不同的是,分解的子问题不是相互独立的,动态规划算法就将子问题的答案记录下来,从而避免同个子问题反复求解的情况;在做题时,通常会思路不够清晰完整,一般是将题目与做过的题对照,若类型差不多就会更加得心应手。

    2.分别列出编程题1、2的递归方程

(1) 求单调递增最长子序列 (时间复杂度为 O(n2))

//没有使用递归

//将数字存于a[]中

    for (int i = 1; i < n; i++){

        for (int j = 0; j < i; j++)

            if (a[j] < a[i]&& b[j]>b[i] - 1)

                b[i] = b[j] + 1;

    }

    int t = b[1];

    for (int  k = 0; k < n; k++)

    {

        if (b[k] > t)

            t = b[k];

    }

    cout<<t;

(2) 租用游艇问题

t=a[i][k]+a[k][j];( k=j-1; k>=i+1 )

①a[i][j]=max{ a[i][j], t } ( j!=i+1 && i>=1 && j<=n )

②a[i][j]=a[i][j] ( j==i+1 )

 算法第三章作业

 

       3.说明结对编程情况

起初在做租用游艇问题时,我们刚开始各自思考,后来思路是一样的,等到编程时,我会漏掉一些东西,经过同伴提醒就作对了。