<commit_before>/**
 *	You are climbing a stair case. It takes n steps to reach to the top.
 *
 *	Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 *
 *	
 *	Author: matao
 *  
 * 	假设n级台阶共An中走法，则：
 *	n = 1时，A1 = 1;  (走1级)
 *  n = 2时，A2 = 2;  (走2个一级或走1个两级)
 *	所以n级台阶，可以走n-1级后再走1级 或 走n-2级后再走2级
 *	An ＝ An-1 + An-2;
 *	1 2 3 5 8...
 */

public class ClimbingStairs {
	// Recursion
	public static int climbStairs1(int n) {
		if(n == 1)
			return 1;
		if(n == 2)
			return 2;
		return climbStairs1(n-1) + climbStairs1(n-2);
    }

    // None-Recursion
    public static int climbStairs2(int n) {
    	if(n == 1)
    		return 1;
    	if(n == 2)
    		return 2;
    	int a = 1, b = 2, sum = 0;
    	for(int i = 3; i <= n; i++) {
    		sum = a+b;
    		a = b;
    		b = sum;
    	}
    	return sum;
    }

    public static void main(String[] args) {
    	System.out.println(climbStairs1(3));
    	System.out.println(climbStairs1(4));
    	System.out.println(climbStairs1(5));
    	System.out.println(climbStairs1(10));

    	System.out.println(climbStairs2(3));
    	System.out.println(climbStairs2(4));
    	System.out.println(climbStairs2(5));
    	System.out.println(climbStairs2(10));
    }
}<commit_msg>optimize Climbing Stairs solution<commit_after>/**
 *	You are climbing a stair case. It takes n steps to reach to the top.
 *
 *	Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 *
 *	
 *	Author: matao
 *  
 * 	假设n级台阶共An中走法，则：
 *	n = 1时，A1 = 1;  (走1级)
 *  n = 2时，A2 = 2;  (走2个一级或走1个两级)
 *	所以n级台阶，可以走n-1级后再走1级 或 走n-2级后再走2级
 *	An ＝ An-1 + An-2;
 *	1 2 3 5 8...
 */

public class ClimbingStairs {
	// Recursion
	public static int climbStairs1(int n) {
		if(n == 1)
			return 1;
		if(n == 2)
			return 2;
		return climbStairs1(n-1) + climbStairs1(n-2);
    }

    // Dynamic Programming
    public static int climbStairs2(int n) {
    	if(n <= 1) {
            return n;
        }
        int pre = 1, ppre = 1;
        int curr = 0;
        for(int i = 2; i <= n; i++) {
            curr = pre + ppre;
            ppre = pre;
            pre = curr;
        }
        return curr;
    }

    public static void main(String[] args) {
    	System.out.println(climbStairs1(3));
    	System.out.println(climbStairs1(4));
    	System.out.println(climbStairs1(5));
    	System.out.println(climbStairs1(10));

    	System.out.println(climbStairs2(3));
    	System.out.println(climbStairs2(4));
    	System.out.println(climbStairs2(5));
    	System.out.println(climbStairs2(10));
    }
}
{'fraction_non_alphanumeric': 0.13919129082426127, 'fraction_numerical': 0.04393468118195956, 'mean_word_length': 2.286079182630907, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6309648', 'n_tokens_mistral': 1172, 'n_tokens_neox': 1152, 'n_words': 256}