1. 对动态规划算法的理解:
动态规划算法和分治法的思想有些类似,感觉都有一种“大事化小,小事化了”的味道,通过将问题规模缩小,然后求解子问题,最后再根据子问题来求解总问题。由于各子问题之间相互独立,可能会出现子问题被重复解决的情况,所以这个时候我们需要建立一个数组来保存我们解决过的子问题的值,也就是备忘录;还有一点就是它和贪心算法的区别,一开始我有点混淆,错误地以为它也是和贪心算法一样,然而并不如此,它得从全局考虑,求各子问题的当前最优解,然后逐步扩大,最终求得总问题的最优解,从全局出发考虑各个最优解,这样最终求得的值才是全局最优解。
2. 编程题1的递归方程:
i个数组成的序列的最长单调递增子序列长度为a[i]
a[i] = max ( a[j] +1, a[i] ) (j<i)
编程题2的递归方程:a[1][n]表示从第一站到第n站所花费的最少的租金,
a[1][n] = min { a[1] [j] + a[j] [n],a[1][n] }(1<j<n)
3. 结对编程的情况
我和另一位队友彦君的话,经常是在看到问题之后先各自花五分钟整理思路,然后再讨论并且合作完成作业,在这个过程中,他给了我很多帮助,我也获益匪浅。