C++ easy to understand recursive solution


  • 0
    D

    We define the function numWays(n, k) to return the number of ways to paint n fences with k colours such that the first fence is always just a single colour and if the first two fences are always a single colour. i.e. Suppose we have 3 colours, (red, green, blue), then we assume that the first fence will always be red, and if the first 2 fences are of the same colour, they are always red.

    Suppose the first fence is always red, then we can determine the number of ways to paint the remaining n-1 fences with colours (green, blue). This gives us (k-1) * numWays(n-1).

    Suppose the first 2 fences are always red, then we can determine the number of ways to paint the remaining n-2 fences with colours (green, blue). This gives us (k-1) * numWays(n-2).

    Hence, the total ways to paint n fences with k colours is k * numWays(n, k).

    The code below probably won't pass the OJ since it's not memoized, but it's easy to memoize it.

    int numWays(int n, int k) {
      // Painting 2 fences such that either the 2nd fence alone
      // is just a single colour, OR the first 2 fences are just a single
      // colour is possible by painting the 2nd fence with 1 colour
      // and the first fence with (k-1) colours, or both fences with
      // the one colour. i.e. ((k-1) + 1) = k.
      if (n == 2) return k;
      if (n == 1) return 1; // Just painting 1 fence with 1 colour.
      if (n < 1) return 0;
      return (k-1) * (numWays(n-1, k) + numWays(n-2, k));
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.