#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */
int string_compare(char *s, char *t, int i, int j)
{
int k; /* counter */
int opt[3]; /* cost of the three options */
int lowest_cost; /* lowest cost */
if (i == 0) return(j * indel(’ ’));
if (j == 0) return(i * indel(’ ’));
opt[MATCH] = string_compare(s,t,i-1,j-1) +
match(s[i],t[j]);
opt[INSERT] = string_compare(s,t,i,j-1) +
indel(t[j]);
opt[DELETE] = string_compare(s,t,i-1,j) +
indel(s[i]);
lowest_cost = opt[MATCH];
for (k=INSERT; k<=DELETE; k++)
if (opt[k] < lowest_cost) lowest_cost = opt[k];
return( lowest_cost );
}
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
动态规划
自顶向下——记忆
递归做了很多不必要的计算，因为给定的斐波那契数将被计算多次。一个简单的改进方法是缓存结果:
cache = {}
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
if n in cache:
return cache[n]
cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
return cache[n]
自底向上
更好的方法是通过按正确的顺序计算结果来摆脱递归:
cache = {}
def fibonacci(n):
cache[0] = 0
cache[1] = 1
for i in range(2, n + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[n]
我们甚至可以使用常数空间，在整个过程中只存储必要的部分结果:
def fibonacci(n):
fi_minus_2 = 0
fi_minus_1 = 1
for i in range(2, n + 1):
fi = fi_minus_1 + fi_minus_2
fi_minus_1, fi_minus_2 = fi, fi_minus_1
return fi
def fib_recursive(n):
if n == 1 or n == 2:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
print(fib_recursive(40))
自上而下:O(n)高效的大输入
def fib_memoize_or_top_down(n, mem):
if mem[n] is not 0:
return mem[n]
else:
mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
return mem[n]
n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))
自底向上:O(n)为简单和小的输入大小
def fib_bottom_up(n):
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
if n == 1 or n == 2:
return 1
for i in range(3, n+1):
mem[i] = mem[i-1] + mem[i-2]
return mem[n]
print(fib_bottom_up(40))
