第三学习总结

一、对动态规划的理解

1. 动态规划是一个把数据量大的事情变成一个个小的任务，而这些任务的完成又先后顺序，小任务的完成服务大任务的完成，将一些不必要的重复工作减少，是用空间去节约时间，因为动态规划需要记录下每一个小任务的结果；
2. 动态规划和分治法的共同点在于处理问题无论规模大小，方法是一样的；
3. 不同点在于任务是否需要用到子任务，或者说更大规模的数据会不会依赖于大任务的完成，大任务的完成依赖于小任务的完成。

 

二、编程题第1、2题的递归方程

1. 最大子序列

                    1+LCS(i+1,j+1)    a[i]=b[j]

LCS（i,j）

                    Max(LSC(i,j+1),LSC(i+1,j))    a[i]!=b[j]

1. 租用游艇问题

 

cost[i][j] = max(cost[i][j], cost[i][k]+cost[k][j])     (1 <= i < n, i < j <= n, i <= k <= j)

 

三、目前编程的情况

　　目前对一些题目的解题还不够清晰，很容易忘记，需要继续编写代码，提高对该方法的理解与应用能力。