3

这是我在解决问题时经常犯的错误。当参数处于最低极端时，我们如何确定递归函数的值是多少。一个例子会有所帮助：

给定 n，找出仅使用 2x1 块来平铺 3xN 网格的方法数。允许旋转块。

DP解决方案很容易找到

f(n)：平铺 3xN 网格的方式数

g(n)：平铺 3xN 网格的方法数，在最右边一列截断 1x1 块

f(n) = f(n-2) + 2*g(n-1)

g(n) = f(n-1) + g(n-2)

我最初认为基本情况是 f(0)=0, g(0)=0, f(1)=0, g(1)=1。但是，这会产生错误的答案。然后我在某处读到 f(0)=1 并将其推断为

平铺 3x0 网格的方式数量是一种，因为只有一种方式我们不能使用任何平铺（2x1 块）。

我的问题是，按照这种逻辑，g(0) 不应该也是一个。但是，在正确的解决方案中，g(0)=0。一般来说，我们什么时候可以说无用的方法是一种？

4

2 回答 2

3

About your specific question of tiling, think this way:

  • How many ways are there to "tile a 3*0 grid"?
    I would say: Just one way, don't do anything! and you can't "do nothing" any other way. (f(0) = 1)

  • How many ways are there to "tile a 3*0 grid, cutting that specific block off"?
    I would say: Hey! That's impossible! You can't cut the specific block off since there is nothing. So, there's no way one can solve the task anyhow. (g(0) = 0)

Now, let's get to the general case:

  • There's no "general" rule about zero cases.
  • Depending on your problem, you may be able to somehow "interpret" the situation, and find the reasonable value. Most of the times (depending on your definition of "ways") number of ways of doing "nothing" is 1, and number of ways of doing something impossible is 0!
  • Warning! Being able to somehow "interpret" the zero case is not enough for the relation to be correct! You should recheck your recursive relation (i.e. the way you get the n-th value from the previous ones) to be applicable for the zero-to-one case as well, since most of the time this would be a "tricky" case.
  • You may find it easier to base your recursive relation on some non-zero case, if you find the zero-case being tricky, or confusing.
于 2013-03-25T15:41:43.820 回答
1
于 2013-03-25T15:08:01.767 回答