Monthly Archives: October 2014

子问题完整性

处理递归问题时,将原问题切割成若干子问题,即要保证完整又要避免重叠。

找零钱问题:
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents)
and pennies (1 cent), write code to calculate the number of ways of representing n
cents.

如下切割将导致子问题重叠:
f(n) = f(n-25) + f(n-10) + f(n-5) + f(n-1)

f(0) = 1: {}
f(5) = 2: {5}, {1,1,1,1,1}
f(9) = 2: {5,1,1,1,1}, {1,1,1,1,1,1,1,1,1}
f(10) = f(0) + f(5) + f(9) = 1 + 2 + 2 = 5,这是错误的

f(10) = 4: {10}, {5, 5}, {1,1,1,1,1,5}, {1,1,1,1,1,1,1,1,1,1}
这是组合问题不是排列问题,{1,1,1,1,1,5}和{5,1,1,1,1,1}是重复的
组合问题要用“计数“的方法来将原问题切割成子问题。
排列问题要用“顺序”的方法来切割,如跳台阶问题: f(n)=f(n-1)+f(n-2),表示从上一步跳到这一步是经过1个台阶或者2个台阶。

正确的切割方法是:
f(n, 25) = sum{f(n-i*25, 10)}, 0<=i<=n/25 f(n, 10) = sum{f(n-i*10, 5)}, 0<=i<=n/10 f(n, 5) = sum{f(n-i*5, 1)}, 0<=i<=n/5 f(n, 1) = 1 f(n,25)表示将原问题切割成(n/25+1)个子问题 使用0个25分硬币, 1个25分硬币,2个25分硬币,3个25分硬币 .... n/25个25分硬币 这样切割是完整的,而且不重叠。