LeetCode — Stair climbing (Dynamic planning)

This topic is the same as the frog jumping step in the offer.

Topic describes

Dynamic programming

The core idea of dynamic programming is that in order to get to step I you have to get to step I-1 and step I-2, and all the possibilities are the sum of those two cases.

var climbStairs = function (n) {
    let dp = [];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n]
};
Copy the code

The title to reflect

In this case, if the direct use of recursive method, is bound to timeout, dynamic programming is a good way to solve this kind of problem. The key of dynamic programming is to list the equation of dynamic programming accurately.