算法第三章作业
组员：高珞洋，何汶珊
你对动态规划算法的理解
之前在学习分治法的时候也有将其和动态规划进行比较，动态规划能够解题的根本要求是原问题可以细分成子问题，且原问题的最优解必包含子问题的最优解。
为了更明确上述条件，从而保证题目能够运用动态规划求解，通常需要两步操作：
- 明确问题具有最优子结构，并分解问题
- 找出递推关系式（状态转移方程），注意初始状态即边界条件
- 利用循环实现递推关系
动态规划的问题的难点就在于求递推关系式，就个人经验而言，有了递推关系式后写代码就比较简单了，大部分的解题时间也是花在求解和弄懂递推关系上
对于求解动态规划的问题，通常需要每次都保留所有可能的最优解。由于构成整体最优解必然包含局部最优解，但是在全部解决方案列出前，我们不能确定当前的最优解就是整体最优解，因此需要对全部方案进行标记。
在代码中，这一部分经常以“填表”的方式出现。我们利用额外的数组保存各个方案的最优解。比如最大子段和中有用maxSum[i]表示从第一个元素开始到以第i个元素为结尾的子段和，在最长公共子序列中用maxsun[i][j]表示a串的前i个字符与b串的前j个字符的最长公共子序列。而我们在分析问题时，在找递推关系之前，就要先明确这个额外的数组保存的是什么样的信息。
//以下内容来自百科
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
此外，动态规划由于由于递推关系的存在，经常出现自顶向下分析，自底向上实现，例如数字三角形问题、最长公共子序列问题等。毕竟我们习惯从整体入手一步步向下细分问题，而程序则没有第一步则无法实现整体。也就是说，在分析时我们需要确定，在某种特定情况下，只有一种最佳选择，然后根据这个最佳选择往前一步推导，在下一步的时候，往往是从多个结果中选择最佳的结果，这点在数字三角形问题中有很明显的体现。
动态规划和分治法都要求问题可分割，区别在于动态规划要求子问题并非相互独立，比如我们总是追求最优解，而子问题的最优解会影响到当前问题的最优解，这点在最短编辑距离中体现明显。
有了递推关系式，为什么不用递归呢？
事实上，有了递推关系后，利用递归是完全能解决问题的，但是它和动态规划相比时间却大大增加，原因就在于递归进行了太多次重复运算。
递归解题的时候，假设我解第n个问题，需要从n-1，n-2...一直解到第1个问题，再将所有结果相加得到第n个问题的解。而这些步骤显然在解第n-1个问题的时候都做过一遍，增加了许多无用开销。
在动态规划中，我们用数组保存最优解，即保存了n-1的最优解，那么当求解第n个问题的时候，直接调用n-1的最优解即可，大大降低了时间复杂度。这也是我们追求利用循环实现递推关系而不用递归的原因。
分别列出编程题1、2的递归方程
3-1单调递增最长子序列
定义ele[i]表示第i个元素，maxSub[i]表示第一个元素到第ele[i]的最长单调递增子序列的长度
从前开始往后扫描，将每个元素作为最后一个元素，求此情况下的最长单调递增子序列的长度，并以此作为一个子问题，即每个maxSub[i]为一个子问题。
在每个子问题中我们仍需要进行扫描，从第一个元素扫到第i-1个数，设扫描的数为j，即0<j<i。
那么我们要做的就是，如果ele[j]<ele[i]，那么理应让当前的递增子序列长度+1。但是直接+1忽略了两次的ele[j]之间可能出现降序的情况，因此需要比较两次的maxSub[j]+1，因为maxSub[j]表示第一个元素到第ele[i]的最长单调递增子序列的长度，而当ele[j]<ele[i]，那么ele[i]必然能加入其中构成新的递增子序列且长度加一，即maxSub[i]=maxSub[j]+1
由此得出递归方程：
maxSub[i] = max{maxSub[j] + 1} (0<j<i，0<i<n)
在代码实现中，需要额外变量来保存max{maxSub[j] + 1}，不过为了图方便，我直接把maxSub[j] + 1放到maxSub[i]中。这样在求解maxSub[i]的时候，maxSub[i]当前的值就表示上一个maxSub[j] + 1，这样就只用比较maxSub[j] + 1 和maxSub[i]了，即：
maxSub[i] = max{maxSub[i], maxSub[j] + 1} (0<j<i，0<i<n)
3-2 租用游艇问题
定义cost[i][j]表示第i个租船点到第j个租船点的费用，min[i]表示从第i个租船点到终点的最小费用
这题一开始采用的算法，需要用到一个二维数组来存储每个租船点到终点的最小费用，但在参考了一些资料之后，发现可以采用更加简洁易懂的算法：
假设第i个租船点到终点的最低费用路径为i-A-B-C-D-n（终点），那么从第A个租船点到终点的最低费用路径肯定是A-B-C-D-n（终点），依此类推，因此可以从终点往前推，即表min[i]从右往前填表
因此表min[i]要内存储的数据为第i个租船点到终点的最低费用，则令min[i]=cost[i][i+1]+min[i+1]，若cost[i][i+2]+min[i+2]<min[i]，则令min[i]=cost[i][i+2]+min[i+2]，反之相反，因此可得递归方程为
min[i]=min{cost[i][j]+m[j],m[i]}，i+1<=j<=n
说明结对编程情况
结对编程老样子分工明确，我负责代码，珊爷辅助，她有问题及时提出，当我能把她讲懂就说明我是真正理解的。偶尔她会有更好的想法，确实能改善程序。
但是在动态规划方面的好处确实很大。有个人在旁面，你可以在边推到递推公式边解释，在分析的同时理清自己的思路，不容易出错。
在敲代码的时候，涉及到递推公式也会询问珊爷此处有无问题，算是二次检查。
在游艇问题中，一开始我用的二维数组保存最优解，也是珊爷表示这个问题和上一个问题很相似，好像可以用一位数组，我也才发现确实如此。
事实证明，在旁边看你敲代码的人并非什么都不会。