递推

递推

斐波那契数列的使用：f(n)=f(n-1)+f(n-2)

经常会出现初始值不同而为此数列的情况

城市路径（P352）：

给出n个城市的二维坐标，d=|xa-xb|+|ya-yb|.你可以跳过一个城市，求跳过后从1到n城市的最小总距离。

Ans=min(f(i-1)+g(i+1)+d(i-1,i+1))//f(i)为前个城市距离之和，g(i)为i到n城市距离之和或者ans=min(ans,sum-d(i,i-1)-d(i,i+1)+d(i-1,i+1))

本题新意在于可以预处理，将二维问题转为O（n）的一维问题

穿越沙漠（P353）：

卡车穿过1000km的沙漠，容量维500km，路途可以设置多个加油点，请问如何设置使油耗最少。

第一个加油点的设置是无法确定的，我们不妨倒推，易只最优情况是第一个存好500L，且距离终点也是500km，那么我们考虑第二个站点的情况。

根据前面的最优情况，第二个站点需要1000L（500L给1点，500L为路程油耗），那么2点距离1点500/3km。

第三点1500L，那么需要开3趟（送给2点1000L），因为油耗原因，k*500>1000,k=3趟（即k趟*油箱量大于存油量）五次往返，所以距离500/5km；

所以f[1]=500 f[2]=f[1]+500/3 .....f[n]=f[n-1]+500/(2*n-1);

约瑟夫环问题的递推思想：

f[1]=0;  f[i]=(f[i-1]+m) mod i; (i>1)

用倒推的思想理解公式，n人，报到(m-1)退出，则第一次m%n退出，变成（n-1）人进行，从m开始（m-1退出），则编号为m、m-1......n-1、0、1、....m-2//注意没有n号//初始化方法——m->0.....

这样就变成了n-1个人的问题，假设我们知道n-1个人是x留存，那么f[n]=(f[n-1]+m)%n.f[1]=0.