Bài toán Fibonacii với thuật toán quy hoạch động
- 1 2 3 5 8 13 …
F(i) = 1 nếu i<=2
= F(i-1) + F(i-2) nếu i>=3
Thuật toán đệ quy tìm số Fibonacii:
int fib(int i)
{
if (i<=2) return 1;
return fib(i-1)+fib(i-2);
}
Thuật toán quy hoạch động tìm số Fibonacii:
int fib(int n)
{
int[] f = new int[n];
f[0]=1;
f[1]=1;
for (int i=2;i<>
f[i]=f[i-1]+f[i-2];
return f[n-1];
}
Thuật toán quy hoạch động tìm số Fibonacii cải tiến:
int fib(int n)
{
int f1=1, f2=1, f=1;
for (int i=3;i<=n;i++) {
f=f1+f2;
f1=f2;
f2=f;
}
return f;
}