Text Justification / Word Wrap dp problem.Unable 在我的递归中找到重叠条件？

Question

阙：https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap

我尝试过的和遇到的问题：我尝试了一种递归方法来解决这个问题。目前，无法找到重叠的子问题。谁能帮助我如何优化、记忆和 modify/update 我的递归方法？。（我认为我的方法是错误的）

方法： 单词在当前行中（当且仅当 space 被留下时）或者将在新行中。

代码流：

Input text = "Cat is on Floor" .
I stored len in an array = [3,2,2,5]

ans(a,b,c) : a: index, b: line (currently no use), c: current line sum

base condn if all elements are over a>=size: return pow(spaceleft,2)

will return min( subproblem(word in current line),subproblem(word in new line)+pow(spaceleft,2))


Initially :     ans(1,1,3)
          ans(2,1,6)     ans(2,2,2)
      ans(3,2,2)      ans(3,2,5)  ans(3,3,2)
      ans(4,3,5)      ans(4,3,5)  ans(4,4,5)

下面的代码在python3.x:

n=6
arr=[3,2,2,5]
size = 4
def ans(a,b,c):
    if(a>=size):
        return pow((n-c),2);
    if(c+arr[a]+1 > n):
        return (pow((n-c),2)+ans(a+1,b+1,arr[a]))
    return (min(ans(a+1,b,c+arr[a]+1),pow((n-c),2)+ans(a+1,b+1,arr[a])))
print(ans(1,1,3))

在此先感谢您抽出宝贵的时间帮助我....

Answer 1

我认为您的表述可能遗漏了一些案例。这肯定很难理解。这是一个似乎得到正确答案的答案。

class LineWrapper:
  def __init__(self, lens, width):
    self.lens = lens
    self.width = width;

  def cost(self, ptr=0, used=0):
    remaining = self.width - used

    # Case 1: No words: Cost is due to partially used line.
    if ptr == len(self.lens):
      return remaining ** 2 if used else 0

    # Case 2: First word of line. Must skip.
    if used == 0:
      return self.cost(ptr + 1, self.lens[ptr])

    # Case 3: Out of space. Must wrap.
    needed = 1 + self.lens[ptr]
    if remaining < needed:
      return remaining ** 2 + self.cost(ptr)

    # Case 4: Min cost of skip and wrap.
    return min(self.cost(ptr + 1, used + needed), remaining ** 2 + self.cost(ptr))

这个公式中的子问题有很多重叠，你的也是。一个简单的示例是宽度为 7 的 [1, 1, 1, 1]。解决方案将尝试将其放在 1、2、3 和 4 行的所有组合上。可能子组合会重复。

为了更清楚地看到这一点，我们可以记忆并检查命中：

  def memo_cost(self, ptr=0, used=0):
    args = (ptr, used)
    print(args)
    if args in self.memos:
      print(f'Memo hit: {args}')
      return self.memos[args]

    remaining = self.width - used

    # Case 1: No words has cost of partially used line
    if ptr == len(self.lens):
      r = remaining ** 2 if used else 0
      self.memos[args] = r
      print(f'Done: {r}')
      return r

    # Case 2: First word of line. Must skip.
    if used == 0:
      r = self.memo_cost(ptr + 1, self.lens[ptr])
      self.memos[args] = r
      print(f'Must skip: {r}')
      return r
   
    # Case 3: Out of space. Must wrap.
    needed = 1 + self.lens[ptr]
    if remaining < needed:
      r = remaining ** 2 + self.memo_cost(ptr)
      self.memos[args] = r
      print(f'Must wrap: {r}')
      return r

    # Case 4: Min cost of skip wrap and wrap.
    r = min(remaining ** 2 + self.memo_cost(ptr), self.memo_cost(ptr + 1, used + needed))
    self.memos[args] = r
    print(f'Min: {r}')
    return r

print(LineWrapper([1, 1, 1, 1], 7).memo_cost())

当运行时，会产生：

$ python3 lb.py
(0, 0)
(1, 1)
(1, 0)
(2, 1)
(2, 0)
(3, 1)
(3, 0)
(4, 1)
Done: 36
Must skip: 36
(4, 3)
Done: 16
Min: 16
Must skip: 16
(3, 3)
(3, 0)
Memo hit: (3, 0)
(4, 5)
Done: 4
Min: 4
Min: 4
Must skip: 4
(2, 3)
(2, 0)
Memo hit: (2, 0)
(3, 5)
(3, 0)
Memo hit: (3, 0)
(4, 7)
Done: 0
Min: 0
Min: 0
Min: 0
Must skip: 0
0

Answer 2

感谢@Gene，我的回答带有备忘录

    n=7
    arr=[3,2,2,5]
    INF = 9223372036854775807
    size = 4
    dp = [[INF for i in range(n+1)] for j in range(size+1)]
    def ans(a,b,c):
        if(dp[a][c]!=INF):
            return dp[a][c]
        if(a>=size):
            dp[a][c] = pow((n-c),2)
            return pow((n-c),2)
        if(c+arr[a]+1 > n):
            dp[a][c] = (pow((n-c),2)+ans(a+1,b+1,arr[a]))
            return dp[a][c]
        dp[a][c] = (min(ans(a+1,b,c+arr[a]+1),pow((n-c),2)+ans(a+1,b+1,arr[a])))
        return dp[a][c]
    print(ans(1,1,3))

Text Justification / Word Wrap dp problem.Unable 在我的递归中找到重叠条件？

Text Justification / Word Wrap dp problem.Unable to find the overlapping condition in my recursion?

algorithm

dynamic-programming

python-3.x