algorithm - 如何实现dp？

我最近遇到一个问题，我被分为两类人：左手和右手（写作风格）。他们都要坐在一排教室里，为了避免任何干扰，他们的手不能碰撞，也就是说，模式可能是lr、ll或rr。
我尝试使用递归（每个座位取l和r的两个分支），但即使行大小为100，计算量也会非常高。
不知怎么的，我需要实现dp来减少计算量。请建议。
编辑：
实际上，有一个矩阵（就像一个教室），其中三种类型（L R B）的人可以坐在没有手碰撞我必须产生能坐的人的最大数量。假设我有一个2x2矩阵，用左，右和双手类型的人来填充，给出了l=0，r=1，b=3。所以一个有效的安排是0行：B R和1行：B -，其中-表示空座位。

最佳答案

实际上，你有一个矩阵这一事实并没有对解决方案产生影响，你可以将它转换成一个数组，而不会失去通用性，因为每个状态都依赖于它的左或右，而不是它的上下一种自下而上的方法：在每种状态下，你有三样东西，你想坐的座位的索引和左边的人。现在我们可以把桌子从右到左填满了答案是L。

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]

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

关于algorithm - 如何实现dp？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34231156/