The number of option to fill a given shape

user_12819327 0
Viewed 102

Given a two 1d arrays that are stick one to the other with n and m lengths , write a recursive algorithm to find the number of ways that this shape could be filled by 1x1 or 1x2 or 2x1 blocks , The arrays that we need to fill

here is my attempt , but I believe that I'm counting the same option several times : 

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));


}

*** UPDATE **** now the code compiles.

Examples : input foo(2,2) output : 21 , the right answer is 7 . input foo(4,3) output : 417, the right answer is 32.

these are the options for foo(2,2).

enter image description here

recursion algorithm java
2 Answers

We'll assume n < m. If this is not the case we can just reverse the arguments - this makes the code simpler.

Once we've dealt with the terminating conditions we use a decrease-and-conquer strategy to reduce the input according to the following rules: if n == m, we can reduce both n & m by 1 two ways, n & m by 2 one way, n by 1 and m by 2 one way, and n by 2 and m by 1 one way. If n < m we can reduce m by 1 one way and m by 2 one way.

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);
}

Test:

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));

Output:

(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

For the case n == m (2, 7, 22, 71, ...) this is a known integer sequence (A030186).

And just for reference, here are the 32 configurations for (3,4):

enter image description here

user_64388190

I believe that i have found the correct answer to my question :

yet i'm not closing this problem until someone with better knowledge than me confirm my answer

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));
   }

   }

now i'm taking only the maximum sub-Problem answer so I won't count the same option more than once.

user_128193270
Related