動的計画法

センテンススクリーンフィッティング



Sentence Screen Fitting



与えられたrows x cols画面とのリストで表される文 空ではない 言葉、見つける 何回 与えられた文を画面に収めることができます。

注意：



  1. 単語を2行に分割することはできません。
  2. 文中の語順は変更しないでください。
  3. 2つの連続した単語 一列に 単一のスペースで区切る必要があります。
  4. 文中の総単語数は100を超えません。
  5. 各単語の長さは0より大きく、10を超えません。
  6. 1≤行、列≤20,000。

例1：

class Solution { public int wordsTyping(String[] sentence, int rows, int cols) { int n = sentence.length int[] dp = new int[n] // Calculate how many words can be stored in a line starting with sentence[i] for(int i = 0 i

例2： 



 Input:  rows = 2, cols = 8, sentence = ['hello', 'world']  Output:  1  Explanation:  hello--- world--- The character '-' signifies an empty space on the screen.

例3： 

 Input:  rows = 3, cols = 6, sentence = ['a', 'bcd', 'e']  Output:  2  Explanation:  a-bcd- e-a--- bcd-e- The character '-' signifies an empty space on the screen.

アイデア：最初に、各単語の先頭に行を格納できる単語の数を計算し、それらをdp配列に格納します。あなたはなぜこれをやっているのですか？最初の単語の前にスペースがないので、計算が完了した直後に長さを呼び出すことができます計算する必要はなく、すべての行に格納できる単語の数、および単語数/文の長さを計算します繰り返し回数です

 Input:  rows = 4, cols = 5, sentence = ['I', 'had', 'apple', 'pie']  Output:  1  Explanation:  I-had apple pie-I had-- The character '-' signifies an empty space on the screen.