java-动态编程斐波那契数列

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-动态编程斐波那契数列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1515字，纯文字阅读大概需要3分钟。

内容图文

我正在学习动态编程在斐波那契数列中的应用,并有一个问题.这是供参考的代码：

import java.math.BigInteger;
import java.util.Arrays;

public class FibonacciNumbersB {

    static BigInteger[] dp = new BigInteger[10000];

    public static void main(String[] args) {
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;

        for(int i = 4; i < 9999; i++)
            System.out.println(fibRecurse(i).toString());
    }

    public static BigInteger fibRecurse(int N) {
        for(int i = 2; i < N; i++) {
            // For numerous calls to this function, this will save as it goes
            if(dp[i].equals(BigInteger.ZERO))
                dp[i] = dp[i - 1].add(dp[i - 2]);
        }

        return dp[N - 1];
    }
}

我有一条语句检查在fibRecurse方法中dp [i]是否等于0(尽管fibRecurse不是递归的).

检查dp [i]是否已经计算过还是仅使dp [i]等于前两个元素的和更有效？

解决方法:

我希望使用Map< Integer,BigInteger>执行此备注时使用固定BigInteger []的问题.请注意,您当前的方法不是递归的.地图可以像这样声明和初始化

static Map<Integer, BigInteger> memo = new HashMap<>();
static {
    memo.put(0, BigInteger.ONE);
    memo.put(1, BigInteger.ONE);
}

然后检查当前n是否存在于备忘录中(如果存在,请返回)-否则,将其存储并存储.喜欢,

public static BigInteger fibRecurse(int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    memo.put(n, v);
    return v;
}

没有备忘录的版本会简单地省略备忘录,例如

public static BigInteger fibRecurseSlow(int n) {
    if (n == 0 || n == 1) return BigInteger.ONE;
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    return v;
}

我认为您可以从我选择的方法名称中推断出速度较慢.

内容总结

以上是互联网集市为您收集整理的java-动态编程斐波那契数列全部内容，希望文章能够帮你解决java-动态编程斐波那契数列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端