[CSE] 10.13

1. 青蛙过河
如图所示，河中间有相同间隔的一系列石子，一只小青蛙要从河的左岸跳到右岸去（图中有六只青蛙，题目中只有一只青蛙:(  ） 小青蛙可以一次跳一颗石头，也可以一次跳两颗石头，小青蛙只能从左往右跳，请问: 给出河中间石头的颗数，求出小青蛙过河总共有多少种方法

Input: N(1<N<100,000) 石子个数
Output: 过河方法的个数
Time Limit: 1s(C++/Java)
Sample Input 1:
2
Sample Output 1:
3
Sample Input 2:
10
Sample Output 2:
144


2. 青蛙过河加强版
过河规则和第一题一样，不过加了一个限制条件：河中间有些石子上面很光滑，小青蛙如果跳到这些石子上会掉到水里过不了河，给出石子个数和光滑石子的编号，求出小青蛙过河的方法数
Input: 
第一行：N石子个数，M其中光滑石子个数 (1 < N&M < 1000000)
第二行：从左往右M个光滑石子的编号，以逗号分隔
Output: 过河方法的个数，如果小青蛙没法过河，输出 -1
Time Limit: 1s(C++/Java)
Sample Input 1:
2 0
Sample Output 1:
3

Sample Input 2:
10 10
1,2,3,4,5,6,7,8,9,10
Sample Output 2:
-1

Sample Input 3:
5 3
1,3,5
Sample Output 3:
1

[Solution].java

public class Solution {
    public int countWays(int n, int[] slips) {
        int[] dp = new int[n + 2];
    	dp[0] = 1;
    	dp[1] = 1;
    	for(int i = 0; i < slips.length; i++){
    		dp[slips[i]] = -1;
    	}
    	for(int i = 2; i <= n + 1; i++){
    		if(dp[i] == -1) continue;
    		int sum = 0;
    		if(dp[i - 1] != -1) sum += dp[i - 1];
    		if(dp[i - 2] != -1) sum += dp[i - 2];
    		dp[i] = sum;
    	}
    	return dp[n + 1] == 0? -1: dp[n + 1];
    }
}

neat!