一、对动态规划算法的理解

• 动态规划算法思想同分治法思想类似，但比分治法更加精炼，通过建立记录表的方式避免多次计算同个子问题。
• 其步骤如下：（1）分析最优解结构（该问题是否符合最优子结构的性质）

　　　　　　　　　（2）确定子问题的递归结构

　　　　　　　　　（3）计算最优值（通过保留已解决问题答案，使得每个子问题只计算一次，输出最优值以及记录最优断开位置）

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

• 编程1：单调递增最长子序列 

  (1)递归方程：len[i]=max(len[i],len[j]+1);  (i>j;a[i]>a[j];a[]为输入的序列）；flag = max(flag,len[i]); （flag初始为0，比较len数组记录的所有最长子序列)

#include 
     
      using namespace std;int main() {    int n,m;    int d=0;    cin>>n;    int a[1000];    for(int i=0;i
      
       >a[i];    }    int len[1000];    for(int i=0;i
       
        a[j]){          len[i]=max(len[i],len[j]+1);        }      }    }    int flag =0;    for(int i=0;i
       
      
     

• 编程2：租用游艇问题 

　　　　　（1）递归方程：b=min(b,(s[i][p]+a[p][j])); (i<p&&p<j&&i<j)

#include 
     
      using namespace std;int s[200][200];void find(int a[][200],int n){    int b;    for(int i=1;i<=n;i++){      s[i][i]=0;    }    for(int i=1; i<=n; i++){        for(int j=i+1; j<=n; j++){          b=a[i][j];        for(int p=i+1;p
      
       >n;  for(int i=1;i<=n;i++){    for(int j=i+1;j<=n;j++){      cin>>a[i][j];    }  }  find(a,n);  cout<
       
        <
       
      
     

 

三、说明结对编程情况

• 动态规划这部分自己掌握的不是很好，动态规划的思想及如何去具体实施，都不是很了解。去问了队友，互相讨论其中的代码，这个过程中学到了很多，一个人的想法总是比不上多个人的，与此同时，因为队友互相讨论，打不出代码的时候没有之前那么慌。