https://leetcode.com/problems/maximize-grid-happiness/
不是很直观的一道DP题目，值得学习一下

个人解答

  1. class Solution:
  2.     def getMaxGridHappiness(self, m: int, n: int, ic: int, ec: int) -> int:
  3.         # 0: no person; 1: introverts; 2: extroverts
  4.         influence = [
  5.             [0, 0, 0],
  6.             [0, -30 * 2, -30 + 20],
  7.             [0, -30 + 20, 20 * 2]
  8.         ]
  9.         happiness = [0, 120, 40]
  11.         @functools.lru_cache(None)
  12.         def f(idx, prevRow, remainIc, remainEc):
  13.             if idx == m * n:
  14.                 return 0
  15.             r, c = idx // m, idx % m
  16.             res = 0
  18.             # 3 conditions, place no person, introvert, extrovert
  19.             for personType, newIc, newEc in [(0, remainIc, remainEc), (1, remainIc - 1, remainEc), (2, remainIc, remainEc - 1)]:
  20.                 if newIc < 0 or newEc < 0:
  21.                     continue
  23.                 # curr happiness
  24.                 val = happiness[personType]
  25.                 # neighbor influence happiness
  26.                 if r > 0:
  27.                     val += influence[personType][prevRow[0]]
  28.                 if c > 0:
  29.                     val += influence[personType][prevRow[-1]]
  30.                 # others' happiness
  31.                 val += f(idx + 1, prevRow[1:] + (personType,), newIc, newEc)
  33.                 res = max(res, val)
  34.             return res
  36.         return f(0, tuple([0] * m), ic, ec)

参考：https://leetcode.com/problems/maximize-grid-happiness/discuss/936467/Python-Short-and-clean-dp-with-diagram-expained

题目分析

做题的时候想着贪心的策略，比如考虑外向的人聚在一起，内向的人尽量分开之类的，但是没有想出来。
当然，更没想到的是，最后的解答是如此暴力的DP，值得学习一下！

先确定dp状态，比较好容易想到的是：

  • 坐标
  • 剩余的两类人的数量

但是这样是不够的，因为邻居间相互影响的关系，还需要记录邻居的状态，而邻居这个东西，不像坐标或者剩余数量这样好记录，这也就是本题的关键了。

首先，不用考虑四个邻居，如果按照坐标从左到右，从上到下来说，当到达某个特定坐标之后，相当于只有之前的，也就是左边和上边的邻居需要考虑，毕竟dp表示的意义就是，在当前状态下的结果，后续的目前可以当作不存在。

其次，对于某一点而言，当前点和后续点受前边的影响，只会受到最后一“行”的影响，这里的最后一行，是指当前点左边的半行，和当前点上边一点到右边的半行。如此，当前及之后点的左侧和上侧所有之前的点都包含在这一“行”中。这个，也就是要考虑的邻居的状态。

所以，对于想这种二维空间上的dp，记录邻居状态，可以学习这种记录前一行的方式！

最后，坐标用一个数 r * m + c，会比r和c两个数好使，因为不用考虑换行的问题，算是一个小tip。

大致就是如此，具体还是要对照代码自己学习。