Climbing Stairs II(ladder)

Description

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Example
n=3
1+1+1=2+1=1+2=3=3
return 4

Link

Lintcode_ladder

Method

1. Dp, permutation without overlapping
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param n an integer
     * @return an integer
     */
    int climbStairs2(int n) {
        // Write your code here
        if (n < 0) {
            return 0;
        }
        if (n < 1) {
            return 1;
        }
        vector<int> climbing = {1, 2, 3};
        vector<int> dp(n+1, 0);
        // for starter, when rest stair = 0
        dp[0] = 1;
        // Similar to backpack
        // Difference: we need to get every possible result then going to next stair
        // Perform: permutation without overlapping 
        //
        // Imp: for loop
        // Stair outer
        // Climbing internal
        //
        // Example: permutation
        // stair = 3, step = 1, 2, 3
        // dp index: [0,  1,  2,  3]
        // init   :   1
        // step 1:       +1  +1   +2   
        // step 2:           +1   +1   
        // step 3:                +1
        // 
        // As we can see, when stair = 3, step = 1, we +2 to dp[3], 
        // actually, we have two ways to reach stair = 2, 
        // Then perform step = 1 to reach stair = 3 
        //      !! ignoring how to reach stair = 2
        // So it is permutation
        for (int stair = 1; stair <= n; ++stair) {
            for (int step = 0; step < climbing.size(); ++step) {
                if (stair >= climbing[step]) {
                    dp[stair] += dp[stair-climbing[step]];
                }
            }
        }
        return dp[n];
    }
};

Similar problems

x

Tags

x