First encounter with dynamic programming

1. You are the guiding algorithm of how to go in every step of my life
2. Mathematically, I call you an ugly mathematical induction , namely k<n-1&&k=n-1 To k<=n The process of .
3. State shift , Repeat the question , The optimal substructure is your core .
4. You always rely on violent algorithms first .
5. It makes ordinary people feel like listing a formula , How to invert parameters step by step , Then the method of finding the optimal solution in this binary result set .
6. Memos are your most common weapon , After using it , You are a different person , Time complexity can reach O(n), It's a tree , However, the complexity is so low .
7. Many people misunderstand you , Think you are recursive , Recursion, however, is a dead end traversal , Your state transition needs a little semantic comfort .
8. You are from the bottom up . From top to bottom tells us to traverse violently from the top . Bottom up is a result of design , And I got an equation that shifts this result , Gradually transfer from the top to the bottom .

Classical problems , climb stairs

Suppose you're climbing the stairs . need n You can reach the top of the building .

Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

/** * @param {number} n * @return {number} */
var climbStairs = function(n) {
    
    // clear dp Array , So-called dp, Is the abbreviation of dynamic programming .
    var dp=[]
    // clear dp Bounds of an array , That is the starting point of our deduction .
    dp[1]=1;
    dp[2]=2;
    // Specially defined variable names , be called tz, The meaning of transfer . there tz The pointer represents 『 state 』 The transfer of .
    var tz = 3;// from 3 At first, it can only climb 1 Step , or 2 Step . The third step is to 「 Calculation 」 了 .
    // I want to climb n rank , I just want to move to n That's all right. .
    while(tz<=n){
    
        dp[tz]=dp[tz-1]+dp[tz-2]; //【  State transition equation 】
        tz++;
    }
    return dp[n]; // Return the result I want 
};