第一章 递归问题

汉诺塔

另T(n)为移动最少次数

则T(n) = T(n-1)[将n-1个盘移到一个柱] + T(n-1)[将剩下的n-1个盘移动到一个柱] +  1 [将大盘移动到最后一个位置]



直线分割问题

画图理解，第n条直线能和前面n-1个直线相交，然后多n个空间出来

拓展问题：用折线“V”代替直线

对于每对折线损失2个空间，因此

约瑟夫环问题

2n（偶数）的情况下，J(2n) = 2J(n)-1

2n+1（奇数）的情况下，J(2n+1) = 2J(n)-1

画图理解，在2n情况下，id = 3要被转换成 id = 2来表示下一轮（下一轮的id从1,3,5,7,2n-1映射成了1,2,3,4...n-1,n），所以J(2n) = 2J(n)-1；2n+1的情况同理，直接记忆化搜索或者分奇偶性直推