Text Fitting Dynamic Programming

Description

Text Fitting
Dynamic Programming

Given a text (a sequence of words) and a container with a certain width and height, find the number of text that can be fitted in the container without splitting any words. There must be a single space between two consecutive words on a line.

The input has 3 lines. The first line is an integer for width. The second line is an integer for height. The third line is a string for text.

Important Info:
You must solve this problem using dynamic programming (DP). If you do not use DP, you will not receive any credit for this assignment.

Example 1:
Input:
2
6
cosc 3320
Output: 1

Explanation: The text is a sequence of 2 words: cosc, 3320
c o s c – –
3 3 2 0 – –
The character ‘-‘ signifies an empty space on the screen.
Example 2:
Input:
3
7
one a bc
Output: 2

Explanation: The text is a sequence of 3 words: one, a, bc
o n e – a – –
b c – o n e –
a – b c – – –

The character ‘-‘ signifies an empty space on the screen.