ACM的一道问题.火车沿途也不是所有站台都停靠,偶尔也是会跳过一些小站的.可以跳过一些小站,但是绝对不能连续跳过两站及以

很简单的动态规划.
dp[i]表示第i个站有多少种方案.
则有：
dp[1]=dp[2]=1;
dp[i]=dp[i-1]+dp[i-2];
以此类推
再问： 为什么，不理解呀，
再答： 很容易理解 第i个站只有两种到达方案 一是在i-1个站然后过了一个站停下的，这时候方案数就是第i-1个站的方案数。 二是第i-2过了两个站停下的，这时候方案数就是第i-2个站的方案数。 所以第i个站的方案数就是 第i-1个站的方案数 + 第i-2个站的方案数 我为了简便用了dp[i]表示第i个站有多少种方案 第一个站和第二个站的方案数显然都是1 则是：dp[1]=dp[2]=1; 后面的站就可以根据前面讲的理由去递推了 即：dp[i]=dp[i-1]+dp[i-2]; 懂了么