מריה בוטוסוב

צריך לעלות n מדרגות. אפשר לעלות 1 או 2 מדרגות ביחד. כמה דרכים יש לעלות את המדרגות? דוגמה: יש 3 דרכים לעלות 3 מדרגות: 1+2, 2+1, 1+1

public int climbStairs(int n) {
    int[] dp = new int[n+1];//Ways to climb stairs
    dp[0] = 1; //0 stairs - 1 way
    dp[1] = 1; //1 stair - 1 way
    
    for(int i = 2; i<=n; i++) { //for each n we will calc number of ways
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}
 
//We can do it faster, without array
public int climbStairs(int n) {
    if(n<=3) return n;
    int a = 1, b = 2, c = 3;
    for(int i = 4; i <=n; i++) {
        a = b;
        b = c;
        c = a + b;
    }
    return c;
}