动态规划

作者: _____西班木有蛀牙 | 来源:发表于2018-07-13 13:11 被阅读18次

Algorithm进阶计划 -- 动态规划（上）
4. 动态规划算法
动态规划 Dynamic Programming
《数据结构与算法之美》27——初识动态规划
算法3：动态规划
动态规划
Dynamic Programming(动态规划)类算法分析随笔
什么是动态规划
斐波那契数列
Swift 算法实战：动态规划

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title>动态规划 - 斐波拉契素组</title>
    </head>
    <body>
        <script type="text/javascript">
            // 递归实现
            function recurFib (n) {
                if (n < 2) {
                    return n;
                } else {
                    return recurFib(n - 1) + recurFib(n - 2)
                }
            }
            
            // 动态规划
            function dynFib (n) {
                var val = [];
                for (var i = 0; i <= n; i++) {
                    val[i] = 0
                }
                if (n ==0) {
                    return 0;
                } else if (n == 1 || n == 2) {
                    return 1
                } {
                    val[1] = 1;
                    val[2] = 1;
                    for (var i = 3; i <= n; i++) {
                        val[i] = val[i - 1] + val[i - 2];
                    }
                    console.log(val);
                    return val[n];
                }
            }
            
            console.log(dynFib(10));
            
            // 动态规划非数组
            function iterFib (n) {
                if (n > 0) {
                    var last = 1;
                    var nestLast = 1;
                    var result = 1;
                    for (var i = 2; i < n; i++) {
                        result = last + nestLast;
                        nestLast = last;
                        last = result;
                    }
                    return result;
                } else {
                    return 0;
                }
            }
            console.log(iterFib(10));
        </script>
    </body>
</html>