javascript 前端动态规划入门，前两天刷题打卡

深碍√TFBOYSˉ_ 2022-08-29 10:24 130阅读 0赞

最近，和组里大佬聊了聊，突然就扯到了算法这块，想当初为了参与比赛，面试等准备了许多的算法题，但现在成为一名社畜之后对这块领域知识接触的变少了，甚至觉得这个没必要做了。

聊着聊着大佬就说了几句：**保持练习，题到做时方恨菜**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center][]

啊确实，过去打开 leetcode 就一股脑儿想着刷题，现在的感受已经变了，当我打开官网，我的手习惯性的用快捷键关闭了当前窗口，并没有刷题的想法了。

与大佬沟通后，还是觉得工作之余得保持刷题的习惯，这个对锻炼思维很有帮助。

> 那么就给自己定一个小目标吧，保持每个工作日 1～2 个题，在 10 月份左右开始参与一些周赛，我觉得还是得参与一些挑战。

对于文章的话，目前主要是记录吧，当我把一系列专题刷完之后，会打算出合集视频吧，也算是自己的总结与回馈，所以趁现在关注我，以后就是老粉啦。

# 动态规划入门 #

动态规划一直是我的弱项，但这个对于思维的提升很有帮助，由于之前是有相关算法经验，所以打算从这块先好好学学，不建议零基础直接跟着我做哈。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center 1][]

## 第一天 ##

### 509. 斐波那契数 ###

[509. 斐波那契数][509.]

/**
     * @param {number} n
     * @return {number}
     */
    var fib = function(n) {
        
        let f = new Array(35);
        f[0] = 0;
        f[1] = 1;
        for(let i=2;i<=35;i++){
        
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    };

### 1137. 第 N 个泰波那契数 ###

[1137. 第 N 个泰波那契数][1137. _ N]

/**
     * @param {number} n
     * @return {number}
     */
    var tribonacci = function(n) {
        
        let dp = new Array(40);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        for(let i=4;i<=37;i++){
        
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        return dp[n];
    };

# 第二天 #

## 70. 爬楼梯 ##

[70. 爬楼梯][70.]

/**
     * @param {number} n
     * @return {number}
     */
    var climbStairs = function(n) {
        
        let dp = new Array(n);
        dp[1] = 1;
        dp[2] = 2;
        for(let i=3;i<=n;i++) {
        
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    };

## 746. 使用最小花费爬楼梯 ##

[746. 使用最小花费爬楼梯][746.]

补充：这个题还是蛮有意思的，难度也上升了一点，我是想着从出发点开始看，要么从下标为 0，要么从 1 开始，那么就都爬一下，每次爬的时候就看下一步或者下两步谁的花费最小，选小的就是了，状态方程如下，i 从第 3 个阶梯开始（下标为 2）

dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);

/**
     * @param {number[]} cost
     * @return {number}
     */
    var minCostClimbingStairs = function(cost) {
        
        let dp = [cost[0], cost[1]];
        for(let i=2;i<cost.length;i++){
        
            dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
        }
        return Math.min(dp[cost.length-1], dp[cost.length-2]);
    };

学如逆水行舟，不进则退

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/398c72cd69a74ef1a62945bee1df35ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/705a790c0bad4821b98939e950fd3b5c.png
[509.]: https://leetcode-cn.com/problems/fibonacci-number/
[1137. _ N]: https://leetcode-cn.com/problems/n-th-tribonacci-number/
[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[746.]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/