Fork me on GitHub

动态规划

发表于 | 分类于 | | 本文总阅读量 次
字数统计: 469 | 阅读时长 ≈ 2

漫画

什么是动态规划

所谓的动态规划就是将复杂问题分解成更小的子问题来解决的优化技术,大事化小，小事化了。

步骤

定义子问题

实现要反复执行而解决子问题的部分

识别并求解出边界条件

题目

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

第一步，假设现在是最后一步，那么有两种情况，一种是你在第八阶，另一种是你在第九阶，假设走到第八阶有X种走法，走到第九阶有Y种走法，那么总共有X+Y种走法，以此类推。递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
F(n) = F(n-1)+F(n-2)  (n>=3)


function step(n){
    if(n < 1){
    
        return 0;
        
    }else if(n == 1){
    
        return 1;
        
    }else if(n == 2){
    
        return 2;
        
    }else {
    
        return step(n-1) + step (n-2);
        
    }
}

上面的解法类似一个二叉树，树的高度是n-1个，节点个数是2的n-1次方，时间复杂度O(2^n);

备忘录算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'use strict';
    var map = {};
    function step(n){
        if(n < 1){

            return 0;

        }else if(n == 1){

            return 1;

        }else if(n == 2){

            return 2;

        }else {
            var value;
            if(map[n-1] != undefined){
                value = map[n-1] + step (n-2);
            }else{
                value = step(n-1) + step (n-2);
                map[n] = value;
            }
            return value;
        }
    }
    console.log(step(10));

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function step(n){
    if(n < 1){
    
        return 0;
    
    }else if(n == 1){
    
        return 1;
    
    }else if(n == 2){
        
        return 2;
        
    }else {
        var a = 1;
        var b = 2;
        var temp = 0;
        
        for(var i=0; i<=n; i++){
            temp = a+b;
            a = b;
            b = temp;
        }
        return temp;
        
    }
}
显示 Gitment 评论