如何实现dp？

Question

我最近遇到了一个问题，我被赋予了两种类型的人:左撇子和右撇子(写作风格)。他们都要坐在班级排上，为了避免任何干扰，他们的手不能碰撞，即图案可以是LR或LL或RR。

我尝试使用递归(每个座位使用L和R的两个分支)，但即使行大小为100，计算量也会非常高。不知何故，我需要实现DP来减少计算量。请提个建议。

编辑：

实际上，有一个矩阵(就像一个教室)，其中可以坐三种类型的人(L，R，B)，而不会发生手部碰撞。我必须生成可以容纳的最大人数。假设我有一个2x2矩阵，为了填充它，给出了左手、右手和双手类型的人L=0，R=1，B =3。因此，一种有效的安排是Row0：B R和row1：B -，其中-表示空白座位。

Answer 1

事实上，你有一个矩阵并不会对解决方案产生影响，你可以将它转换成一个数组，而不会失去一般性，因为每个状态都依赖于它的左或右，而不是它的上和下。自下而上的方法:在每个状态中，你有三个东西L，B和R，你想要填充的座位的索引和它的左边的人。现在我们可以从右到左填充表。答案是dp[inedx=0][L][B][R][left_person=' ']。

recursive [index][L][B][R][left_person] :
  if left_person = ' ' or 'L':
    LVal = recursive[index+1][L-1][B][R]['L']
  if left_person = ' ' or 'L' or 'R'
    RVal = recursive[index+1][L][B][R-1]['R']
  if left_person = ' ' or 'L':
    BVal = recursive[index+1][L][B-1][R]['B']
  NVal = recursive[index+1][L][B][R][' ']
  max(LVal, RVal, BVal, NVal) -> dp[index][L][B][R][left_person]

当然，这不是完整的，我只是给你一个大概的想法。你应该添加一些细节，比如基本情况，并在分配它之前检查是否还有这种类型的人以及其他一些细节。