薛健课后习题

2019年1月17日 下午4:00

循环右移.cpp

1. 时间复杂度最优为O(n)。由于我们这道题限制了使用的空间为1，所以我们不可以直接算出a位置上的元素对应的位置b：（a+k+1）%n=b，这个过程就要使用a,b这两个变量不满足题意。因此，使用序列逆序的方法，进行求解，基本操作是交换两个元素，时间复杂度为O(n)。

   递归：

   00.tar.gz
   算法作业1.ipynb

   分治：

   多米诺骨牌Exercise (3).cpp
2. 思路总结：这道题如果要使用分治法来解决的话，难点在于如何进行合并。并且，这道题中，对于不同的合并范围，有不同合并方式。我们要对int a~b范围内的骨牌进行计算，如果a=b,a=b-1,a=b-2,a<b-2,这四种情况有不同的合并方式，所以代码写起来十分的冗余。在分治的前提下，我现在也没有找到合适的方法进行简化。

动态规划

多米诺骨牌动态规划版.cpp

1. 有些分治算法是改不成动态规划的，原因：在分治和动态规划中最关键的点是划分出子问题，但是有些子问题之间有依赖关系，但是有些子问题就没有，eg:这道题中我原先采用子问题是：对半分方法，左右各一半【按物理位置分类】。写成递归树，或者子问题图，发现【并没有重复解决的子问题】
2. 这时，我们就无法改成动态规划的算法。这里的子问题图并不是向fib问题一样，是一条线性的子问题图，而是一个中心拓扑的结构。
3. 说明，【我们的子问题设计的不成功】
4. 修改后的子问题是：m(s,i)：当第i块骨牌状态为s时，求max(sum(R[k]L[k+1]),他的时间复杂度就是一个循环，所以为O(n)
5. 解决的问题就变成了：max(m[0][n],m[1][n])
6. 2019年7月4日补充：
   1. 【子问题之间的关系是什么？】
      1. 下一个子问题，以上一个子问题的答案为基础
   2. 【子问题与最终问题之间的关系是什么？】
      1. 在这题中，最后一个子问题max(m[0][n],m[1][n])，就是最终问题

         贪心

         邮局位置.cpp
7. 贪心的难点是：千万别追求完美、从大局考虑。我们要做一直鼠目寸光的人，根据当前条件选择最好的，走一步算一步。
8. 思路总结：这里要求复杂度为O(n)，根据这个要求我们知道我们必须在遍历每个房子的时候，能够直接判断出是否需要在当前房子后100米处放邮局。在我的程序中，我设置int index来标志从左到右最后一个需要放邮局的位置，这样我们就可以通过index直接判断