LC 1605. 给定行和列的和求可行矩阵
从数据量规模上看，这题肯定不是使用回溯方法，此外似乎也没有办法猜测每个元素，比如就没有方法猜测a[0][0]是什么。
这题解法还是通过保持不变量来不断修正剩余行/列上的元素的。假设 rowsum=[R0,R1,R2..Rn], colsum=[C0,C1,…Cm]， 我们可以先初始化矩阵为下面这样。
| R0 | 0 | 0 | … | 0 |
| R1 | 0 | 0 | … | 0 |
| R2 | 0 | 0 | … | 0 |
| … | 0 | 0 | … | 0 |
| Rn | 0 | 0 | … | 0 |
这个矩阵在每行上的和始终是满足rowsum要求的，假设我们就是要不断地修正列，但同时保证行和始终是rowsum.
如果我们分析第一列，假设R0+R1 < C0, 但是R0+R1+R2 > C0，因为要求每个元素都是非负整数，所以情况就会变成这样。
| R0 | 0 | 0 | … | 0 |
| R1 | 0 | 0 | … | 0 |
| C0-R0-R1 | R2-(C0-R0-R1) | 0 | … | 0 |
| 0 | R3 | 0 | … | 0 |
| 0 | R4 | 0 | … | 0 |
| 0 | … | 0 | … | 0 |
| 0 | Rn | 0 | … | 0 |
这个时候第一列满足条件，并且行和也始终等于rowsum. 依次类推，接着我们调整剩余的列。
class Solution:
def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
n = len(rowSum)
m = len(colSum)
ans = [[0] * m for _ in range(n)]
# 保证行之和始终满足，开始调整列
for i in range(n):
ans[i][0] = rowSum[i]
for j in range(m):
acc = 0
for i in range(n):
acc += ans[i][j]
if acc > colSum[j]:
delta = acc - colSum[j]
ans[i][j + 1] += delta
ans[i][j] -= delta
acc -= delta
return ans