神刀安全网

Dynamic Programming – How many ways to connect the pipes?

This is an interesting problem that can be solved using Dynamic Programming (DP) . The question is to count how many ways to connect the pipes like the following (Pipes flow 1 direction and cannot overlap each other)

sub-problem-connecting-pipes

As shown above, we have a 4-numbered pipes in the order (from top to bottom, or left to right which doesn’t matter). The requirement is to merge these pipes into 1 flow, and in 2D, these connections should not overlap meaning that we cannot connect pipe 1 to pipe 3 directly because the connection will intersect the pipe 2. We can easily observe that the first steps are to connect the adjacent pipes.

We can easily come up that if we have 0 or 1 pipes, the answer is 0, if we have 2 pipes, the answer is 1. And if we have 3 pipes, there are 2 ways. So below are the case for four pipes.

sub-problem-pipe

Four pipes can have 5 possibilities, as shown above, in which, Case A and Case D are symmetric. Case C and E are symmetric.

If we use f(n) to denote the answer for n pipes, as said above, we have these known conditions:

f(0) = 0; f(1) = 0; f(2) = 1; f(3) = 2;
f(0) = 0; f(1) = 0; f(2) = 1; f(3) = 2;

The lighter blue boxes are the case for f(n-1) while the darker blue box is the case for f(n-2) . It is also seen that the f(n-1) has their symmetrical solutions that is why we need to multiple by two.

So up to this point, the DP recurrence is obvious:

for any n

larger or equal to 3.

You can do it usingrecursion +memorization but aiterative implementation seems trivial.

function CountPipes(int n) {   int a = 0;   int b = 1;   if (n <= 1) return 0;   if (n == 2) return 1;   for (int i = 3; i <= n; i ++) {      int c = a + 2 * b;      a = b;      b = c;   }   return b; }
function CountPipes(int n) {   int a = 0;   int b = 1;   if (n <= 1) return 0;   if (n == 2) return 1;   for (int i = 3; i <= n; i ++) {      int c = a + 2 * b;      a = b;      b = c;   }   return b; }

And the first few numbers are:

for (int i = 0; i <= 6; i ++) {     cout << "f(" << i << ") = " << CountPipes(i) << endl; }
for (int i = 0; i <= 6; i ++) {     cout << "f(" << i << ") = " << CountPipes(i) << endl; }

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Dynamic Programming – How many ways to connect the pipes?

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址