[Solved]Lego Links External Site Links External Site Inspires Develops Builders Tomorrow Example 2 Q37026017

Lego (Links to an external site.)Links to an external site.inspires and develops the builders of tomorrow. An example of a2-by-4 lego brick looks like the following:

(Imagine a lego brick with 2 humps wide by 4 humps long)

You have a set of them, each with a varying height denominations(in red): 2x4x1, 2x4x4, 2x4x8, etc. You are asked to build a wallof a certain target height using an unlimited supply of thesebricks. Write a function to output the number of possible ways(namely, total combination) you can use these bricks to build up awall of target_height. For the sake of illustration, these heightsare unit-less; they are relative to the size of 2×4):

int getLegoCombinations(vector<int> &lego_heights, int target_height)

Examples:

input: {1,2,5}, 3

output: 2

Explanation: you have 3 lego bricks of height 1, 2, and 5,respectively. You are asked to build a wall of height 3. There are2 ways (output) to accomplish this by stacking up your bricks likethis: {1,1,1}, {1,2}. Note the piece with height 5 is never usedbecause its use is not possible.

input: {1,2,5}, 0

output: 0

Explanation: there is nothing to build (target height of 0),hence returning 0.

input: {1,2,5}, 7

output: 6

Explanation: there are 6 possible ways as follows:

{1,1,1,1,1,1,1}

{1,1,1,1,1,2}

{1,1,1,2,2}

{1,2,2,2}

{1,1,5}

{2,5}

input: {5}, 9

output: 0

Explanation: height denomination provided can never reach 9,hence returning 0.

Constraints / Assumptions:

• Input vector with integral denominations of lego_heights isnever empty.

• 0 <= target_height <= INT_MAX.

• lego_height is always integral and >= 1.
• Your lego supply (of indicated denominations) isunlimited.
• HINT: this solution calls for Dynamic Programming. Given aninteger array, solutions, where solutions[target_height] is thetotal combination at the target height, your answer should beobtained via solutions[target_height – height#1] +solutions[target_height – height#2] + solutions[target_height -height#3] + ….

• You should submit a fully working console program however yourmain() function isn’t graded; only the above referenced functionis.

Expert Answer

---

Answer to Lego (Links to an external site.)Links to an external site. inspires and develops the builders of tomorrow. An example o… . . .