Answer to Question #282478 in C for Nnn

Question

How to Attempt?

Charles and the Necklace

Charles wants to buy a necklace in which:

1. There is a minimum of 1 pearl and maximum of X pearls such that

each pearl has its own magnificent coefficient. 2. The pearls should be in non-decreasing order of their magnificence power.

You are given the maximum number of pearls in a necklace and the range of the magnificent coefficients of the pearls. Find the number of necklaces that can be made that follow the mentioned conditions.

Answer 1

#include <bits/stdc++.h>
using namespace std;
int
main ()
{
  int sol (int n, int lm, int hm)
  {


    vector < vector < int >>dp (n, vector < int >(hm - lm + 1, 1));
    int ans = hm - lm + 1 + n - 1;


    for (int i = 1; i < dp[0].size (); i++)
      {
	dp[0][i] += dp[0][i - 1];
      }


    for (int i = 1; i < n; i++)
      {
	for (int j = 1; j < dp[0].size (); j++)
	  {
	    ans += dp[i - 1][j];
	    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
	  }
      }


    return ans;
  }
}