Redirecting to
NADOS


  Prev   Next

Count of Valleys and Mountains







I don't believe you have to be better than everybody else. I believe you have to be better than you ever thought you could be
~Ken venturi

Count of Valleys and Mountains

Welcome Back Reader!

In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Count of Valleys and Mountains".

Importan Link : Problem Link , Question Video Link, Solution Video Link

Before you move any further, it is advised that you give this problem a fair try. Let's jump to the problem.

Understanding the problem:

In this problem you are given a number n, representing the number of upstrokes and number of downstrokes.

All you are required to do is to find the number of valleys and mountains you can create using stroke.

Note: At no point should we go below the sea-level. (number of downstrokes should never be more than number of upstrokes).

For example:

Sample Input: 3

Sample Output: 5

Look at the figure:

img

For more clarity of the question, watch this part of the video.

Approach
  • In this problem we need to find the number of valleys and mountains which can be created using a given number of strokes.
  • This problem is just another application of Catlan Number.
  • So we will use the Catlan Number approach to solve this problem.
  • For input 0, we assume that the output is 1.
  • For input 1, it implies that we have 1 upstroke and 1 downstroke i.e. one pair and we can arrange this in only one way.
    • img
  • For input 2, we have 2 pairs. We can either put one pair inside another pair or not. This way we can arrange 2 pairs in two ways.
    • img
    For input 3, we have 3 pairs. We can arrange these 3 pairs in 3 ways.
    • To start with, we can place 2 pairs inside 1 pair.
    • can also place 1 pair inside 1 pair and one outside it.
    • We can also place 0 pairs inside 1 pair and 2 pairs outside.
      • img
    • If we place 2 pairs inside one pair then we have two ways to do so.
    • If we place 1 pair inside 1 pair and one outside then we have only one way to do so.
    • And if we place 0 pairs inside 1 pair and 2 pairs outside then again we can do this in two ways.
    • In total we will have 5 different ways which is also the output for 3.
  • So from the above points, we can analyze that the problem is following catalan pattern.
    • img
  • Let's see for input 4.
  • For input 4, we have 4 pairs. We can arrange these 4 pairs in 4 ways.
    • To start with, we can place 3 pairs inside 1 pair and 0 outside it.
    • We can also place 2 pairs inside 1 pair and 1 outside it.
    • We can also place 1 pair inside 1 pair and 2 pairs outside it.
    • We can also place 0 zero pairs inside 1 pair and 3 pairs outside it.
      • img
    • If we place 3 pairs inside one pair then we have five ways to do so.
    • If we place 2 pairs inside 1 pair and 1 pair outside then we have only two ways to do so.
    • If we place 1 pair inside 1 pair and 2 pairs outside then we have only two ways to do so.
    • If we place 0 pairs inside one pair and 3 pairs outside it then we have five ways to do so.
    • And if we place 0 pairs inside 1 pair and 2 pairs outside then again we can do this in two ways.
      • img

For more clarity of this part; watch this part of the video.

Let's try to code this!
img
img
  1. Take input for n.
  2. After that define an array, dp of long type and length n+1.
  3. Then we place 1 at dp[0]
  4. Then we apply a for loop on dp length, initializing i to 1
  5. Now we use a nested for loop to calculate the value for ith index of dp by travelling the filled dp array.
  6. Then inside the nested for loop, at dp[i], keep adding dp[j] * dp[i - 1 - j].
  7. At last, print dp[n].

For more clarity of this part, watch this part of the video.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long[] dp = new long[n + 1]; dp[0] = 1; for(int i = 1; i < dp.length; i++){ for(int j = 0; j < i; j++){ dp[i] += dp[j] * dp[i - 1 - j]; } } System.out.println(dp[n]); } }
java; true";

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!

Arrays
Author: Nikita Aggarwal
 
Run
Id Name