算法-动态规划

在牛客网做题时遇到个很简单的题，即求斐波那契(Fibonacci)数列的第n项。我一看，这太简单了， 不就是一个递归解决的事吗。然后。。。就没有然后了。事实证明，这道题用递归算法太浪费资源了，效率也不高。于是 看了下大神代码，说是用动态规划解决，效率之高令我汗颜，因此在网上了解了下动态规划思想。然而我发现这是个挺 复杂的东西，或许是我没弄明白吧，总之今天先记录所得，虽不完整亦为收获。

动态规划

动态算法的核心是记住已经求过的解。而记住已经求过的解有两种方式：自顶向下的备忘录 和自底向上。

自顶向下的备忘录方式也要用到递归，这里暂且不表。重点来谈谈自底向上的方法。

简单来说，自底向上就是先把必定要算出来的子算法先求出来，再通过子算法层层往上。对于Fibonacci数列来说， 求其第n项，那么第n-1项都是必须要求的，而求其第n-1项，第n-2项也是必求的。。。。最底层的就是第0项了.代码如下

                public static int fib(int n)
                {
                        if(n<=0)
                            return n;
                        int []Memo=new int[n+1];
                        Memo[0]=0;
                        Memo[1]=1;
                        for(int i=2;i<=n;i++)
                        {
                            Memo[i]=Memo[i-1]+Memo[i-2];
                        }       
                        return Memo[n];
                }               

优化后代码如下

            class Solution
            {
                public int Fibonacci(int n)
                {
                    int p = 0;
                    int f = 1;
                    while(n-- != 0){
                        p += f;
                        f = p - f;
                    }
                    return p;
                }
            }           

详细内容见HankingHu的博客

算法-动态规划

原文：https://www.cnblogs.com/damocleses/p/10665963.html