动态规划是一种算法范式，它通过将给定的复杂问题分解为子问题来解决，并存储子问题的结果，以避免再次计算相同的结果。下面是一个问题的两个主要性质，它们表明给定的问题可以用动态规划来解决。
null
在本文中，我们将详细讨论第一个属性（重叠子问题）。动态规划的第二个性质将在下一篇文章中讨论。 第二组 . 1) 重叠子问题 2) 最优子结构
1） 重叠子问题： 像分而治之一样，动态规划结合了子问题的解决方案。动态规划主要用于反复需要相同子问题的解时。在动态规划中，子问题的计算解存储在一个表中，这样就不必重新计算。因此，当没有公共（重叠）子问题时，动态规划是没有用处的，因为如果不再需要解决方案，存储它们就没有意义了。例如 二进制搜索 没有常见的子问题。如果我们以斐波那契数的递归程序为例，有许多子问题需要一次又一次地解决。
C
/* a simple recursive program for Fibonacci numbers */ int fib( int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } |
JAVA
/*package whatever //do not write package name here */ /* a simple recursive program for Fibonacci numbers */ static int fib( int n) { if (n <= 1 ) return n; return fib(n - 1 ) + fib(n - 2 ); } // This code is contributed by umadevi9616 |
python
# a simple recursive program for Fibonacci numbers def fib(n): if n < = 1 : return n return fib(n - 1 ) + fib(n - 2 ) |
C#
/* a simple recursive program for Fibonacci numbers */ static int fib( int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // This code contributed by umadevi9616 |
Javascript
<script> /*package whatever //do not write package name here */ /* a simple recursive program for Fibonacci numbers */ function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // This code is contributed by gauravrajput1 </script> |
用于执行 fib（5）
fib(5) / fib(4) fib(3) / / fib(3) fib(2) fib(2) fib(1) / / / fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / fib(1) fib(0)
我们可以看到函数fib（3）被调用了两次。如果我们存储了fib（3）的值，那么我们可以重用旧的存储值，而不是再次计算它。有以下两种不同的方法来存储这些值，以便可以重用这些值： a） 记忆化（自上而下） b） 制表（自下而上）
a） 备忘录（自上而下）： 问题的记忆程序类似于递归版本，只需稍加修改，即可在计算解决方案之前查看查找表。我们初始化一个查找数组，所有初始值都为NIL。每当我们需要子问题的解决方案时，我们首先查看查找表。如果存在预计算的值，那么我们将返回该值，否则，我们将计算该值并将结果放入查找表中，以便以后可以重用。
下面是第n个斐波那契数的记忆版本。
C++
/* C++ program for Memoized version for nth Fibonacci number */ #include <bits/stdc++.h> using namespace std; #define NIL -1 #define MAX 100 int lookup[MAX]; /* Function to initialize NIL values in lookup table */ void _initialize() { int i; for (i = 0; i < MAX; i++) lookup[i] = NIL; } /* function for nth Fibonacci number */ int fib( int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n - 1) + fib(n - 2); } return lookup[n]; } // Driver code int main() { int n = 40; _initialize(); cout << "Fibonacci number is " << fib(n); return 0; } // This is code is contributed by rathbhupendra |
C
/* C program for Memoized version for nth Fibonacci number */ #include <stdio.h> #define NIL -1 #define MAX 100 int lookup[MAX]; /* Function to initialize NIL values in lookup table */ void _initialize() { int i; for (i = 0; i < MAX; i++) lookup[i] = NIL; } /* function for nth Fibonacci number */ int fib( int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n - 1) + fib(n - 2); } return lookup[n]; } int main() { int n = 40; _initialize(); printf ( "Fibonacci number is %d " , fib(n)); return 0; } |
JAVA
/* Java program for Memoized version */ public class Fibonacci { final int MAX = 100 ; final int NIL = - 1 ; int lookup[] = new int [MAX]; /* Function to initialize NIL values in lookup table */ void _initialize() { for ( int i = 0 ; i < MAX; i++) lookup[i] = NIL; } /* function for nth Fibonacci number */ int fib( int n) { if (lookup[n] == NIL) { if (n <= 1 ) lookup[n] = n; else lookup[n] = fib(n - 1 ) + fib(n - 2 ); } return lookup[n]; } public static void main(String[] args) { Fibonacci f = new Fibonacci(); int n = 40 ; f._initialize(); System.out.println( "Fibonacci number is" + " " + f.fib(n)); } } // This Code is Contributed by Saket Kumar |
python
# a program for Memoized version of nth Fibonacci number # function to calculate nth Fibonacci number def fib(n, lookup): # base case if n < = 1 : lookup[n] = n # if the value is not calculated previously then calculate it if lookup[n] is None : lookup[n] = fib(n - 1 , lookup) + fib(n - 2 , lookup) # return the value corresponding to that value of n return lookup[n] # end of function # Driver program to test the above function def main(): n = 34 # Declaration of lookup table # Handles till n = 100 lookup = [ None ] * 101 print "Fibonacci Number is " , fib(n, lookup) if __name__ = = "__main__" : main() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program for Memoized versionof nth Fibonacci number using System; class GFG { static int MAX = 100; static int NIL = -1; static int [] lookup = new int [MAX]; /* Function to initialize NIL values in lookup table */ static void initialize() { for ( int i = 0; i < MAX; i++) lookup[i] = NIL; } /* function for nth Fibonacci number */ static int fib( int n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n - 1) + fib(n - 2); } return lookup[n]; } // Driver code public static void Main() { int n = 40; initialize(); Console.Write( "Fibonacci number is" + " " + fib(n)); } } // This Code is Contributed by Sam007 |
Javascript
<script> let MAX = 100; let NIL = -1; let lookup = new Array(MAX); function _initialize() { for (let i = 0; i < MAX; i++) lookup[i] = NIL; } function fib(n) { if (lookup[n] == NIL) { if (n <= 1) lookup[n] = n; else lookup[n] = fib(n-1) + fib(n-2); } return lookup[n]; } let n = 40; _initialize(); document.write( "Fibonacci number is" + " " + fib(n)+ "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出
Fibonacci number is 102334155
b） 表格（自下而上）： 针对给定问题的列表程序以自下而上的方式构建一个表，并返回表中的最后一个条目。例如，对于相同的斐波那契数，我们首先计算fib（0），然后计算fib（1），然后计算fib（2），然后计算fib（3），依此类推。所以从字面上说，我们是在自下而上构建子问题的解决方案。
下面是第n个斐波那契数的列表版本。
C++
/* C program for Tabulated version */ #include <stdio.h> int fib( int n) { int f[n + 1]; int i; f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } int main() { int n = 9; printf ( "Fibonacci number is %d " , fib(n)); return 0; } |
JAVA
/* Java program for Tabulated version */ public class Fibonacci { int fib( int n) { int f[] = new int [n + 1 ]; f[ 0 ] = 0 ; f[ 1 ] = 1 ; for ( int i = 2 ; i <= n; i++) f[i] = f[i - 1 ] + f[i - 2 ]; return f[n]; } public static void main(String[] args) { Fibonacci f = new Fibonacci(); int n = 9 ; System.out.println( "Fibonacci number is" + " " + f.fib(n)); } } // This Code is Contributed by Saket Kumar |
python
# Python program Tabulated (bottom up) version def fib(n): # array declaration f = [ 0 ] * (n + 1 ) # base case assignment f[ 1 ] = 1 # calculating the fibonacci and storing the values for i in xrange ( 2 , n + 1 ): f[i] = f[i - 1 ] + f[i - 2 ] return f[n] # Driver program to test the above function def main(): n = 9 print "Fibonacci number is " , fib(n) if __name__ = = "__main__" : main() # This code is contributed by Nikhil Kumar Singh (nickzuck_007) |
C#
// C# program for Tabulated version using System; class GFG { static int fib( int n) { int [] f = new int [n + 1]; f[0] = 0; f[1] = 1; for ( int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } public static void Main() { int n = 9; Console.Write( "Fibonacci number is" + " " + fib(n)); } } // This Code is Contributed by Sam007 |
Javascript
<script> // Javascript program for Tabulated version function fib(n) { var f = new Array(n + 1); var i; f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } // Driver code var n = 9; document.write( "Fibonacci number is " + fib(n)); // This code is contributed by akshitsaxenaa09 </script> |
PHP
<?php // PHP program for Tabulated version function fib( $n ) { $f [ $n + 1]=0; $i ; $f [0] = 0; $f [1] = 1; for ( $i = 2; $i <= $n ; $i ++) $f [ $i ] = $f [ $i - 1] + $f [ $i - 2]; return $f [ $n ]; } // Driver Code $n = 9; echo ( "Fibonacci number is " ); echo (fib( $n )); // This code is contributed by nitin mittal. ?> |
输出
Fibonacci number is 34
表格和备忘录都存储子问题的解决方案。在备忘版中，表格按需填写，而在制表版中，从第一个条目开始，所有条目逐个填写。与表格版本不同，查找表的所有条目不一定都填写在备忘录版本中。例如 记忆解决方案 关于 LCS问题 不一定要填写所有条目。
要查看记忆化和表格化解决方案相对于基本递归解决方案的优化效果，请参阅以下计算第40个斐波那契数的运行时间： 递归解 记忆解决方案 表列溶液 递归方法所花费的时间远远超过上面提到的两种动态编程技术——记忆和制表！
此外，请参见 难看的数字柱 举一个简单的例子，我们有重叠的子问题，我们存储子问题的结果。
我们将在以后的动态规划文章中讨论最优子结构性质和一些更多的例子问题。
尝试以下问题作为本文的练习。 1） 为LCS问题编写一份备忘录解决方案。请注意，CLRS手册中给出了表格解决方案。 2） 你会如何在记忆和制表之间做出选择？
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。 参考资料： http://www.youtube.com/watch?v=V5hZoJ6uK-s
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
