填充给定形状的选项数量

Question

给定两个长度为n和m的1d数组，写一个递归算法，求这个形状可以由1x1或1x2或2x1块填充的方式数。

这是我的尝试，但我相信，我计数相同的选项几次。

public static int foo(int n1 ,int m){
if(n1==0 &&  m ==0){
    return 1;
}
if(n1 < 0 || m < 0)
    return 0;

  return (foo(n1-1,m)+foo(n1,m-1)+foo(n1-1,m-1) +foo(n1,m-2) + foo(n1-2,m));


}

***更新 ****现在代码编译。

例子：输入foo(2,2)输出：21，正确答案是7.输入foo(4,3)输出：417，正确答案是32。

这些是foo(2,2)的选项。

Answer 1

我们将假设 n < m. 如果不是这种情况，我们可以把参数反过来--这使得代码更简单。

一旦我们处理了终止条件，我们就使用递减和征服策略，根据以下规则减少输入：if n == m，我们可以减少两个 n & m 由1两种方式。n & m 由2个单程。n 1和 m 由2个单程，和 n 以2和 m 由1单程。如果 n < m 我们可以减少 m 单程 m 由2个单程。

static int foo(int n, int m)
{           
    if(n > m) return foo(m, n);

    if(n < 0 || m < 0) return 0;

    if(n == 0 && m == 0) return 1;

    if(n == m) return 2*foo(n-1, m-1) + foo(n-2, m-2) + foo(n-1, m-2) + foo(n-2, m-1);

    return foo(n, m-1) + foo(n, m-2);
}

测试：

for(int i=0; i<5; i++)
    for(int j=i; j<5; j++)
        System.out.format("(%d, %d) = %d%n", i, j, foo(i, j));

输出。

(0, 0) = 1
(0, 1) = 1
(0, 2) = 2
(0, 3) = 3
(0, 4) = 5
(1, 1) = 2
(1, 2) = 3
(1, 3) = 5
(1, 4) = 8
(2, 2) = 7
(2, 3) = 10
(2, 4) = 17
(3, 3) = 22
(3, 4) = 32
(4, 4) = 71

对于这种情况 n == m (2，7，22，71，...)这是一个已知的整数序列(A030186).

仅供参考，以下是(3,4)的32种配置。

Answer 2

我相信我已经找到了我的问题的正确答案。

然而，我不会关闭这个问题，直到有人比我有更好的知识确认我的答案。

public static int foo(int n1 ,int m){
   if(n1==0 &&  m ==0){
  return 1;
 }
   if(n1 < 0 || m < 0)
      return 0;
  if(m == n1){
    return Integer.max(foo(n1-1,m),foo(n1,m-1)) + Integer.max(foo(n1-2,m),foo(n1,m-2))+ foo(n1-1,m-1);
  }else{
   return Integer.max(foo(n1-1,m),foo(n1,m-1)) + Integer.max(foo(n1-2,m),foo(n1,m-2));
   }

   }  

现在，我只取最大的子问题答案，所以我不会把同一个选项计算一次以上。