给定一个二维数组，从(0,0)开始，在x和y轴正方向上一直到无穷大。给定一个数k>0，求从(0,0)可到达的单元数，使得在每一时刻->x的位数之和+y<k移动可以是向上、向下、向左或向右。给定x，y>=0
Dfs给出了答案，但对于k的大值来说还不够。有人能帮我找到更好的算法吗？
我想他们要求您计算k>=x+y可到达的单元数(x，y)。例如，如果x＝1，那么y可以取0和k-1之间的任何数字，并且总和将<k.可能性的总数可以通过来计算
sum(sum(1,y=0..k-x),x=0..k) = 1/2*k²+3/2*k+1
这应该能够为大k做技巧。
我对你问题中的"数字"有些困惑。这些数字组成了索引，就像3乘以9等于999。单元格(999888)的位数总和将是51。如果允许数字之和为10^9，则索引可能有10^8个数字，从而产生大约10^(10^8)个条目，远远超过表的正常大小。因此，我假设我的第一种解释。如果这不正确，你能再解释一下吗？
编辑：
好吧，我的答案不会解决问题。恐怕我看不到一个好的公式或答案。我会把它当作一个着色/标记问题来处理，标记所有有效的单元格，然后使用其他技术来确保所有部分都连接/计数。
我试着想办法，但是太乱了。基本上，我会尝试根据索引和k一次标记大的部分。如果k=20，你可以一次标记单元格范围(0,0..299)(因为任何较低的索引都会有较低的索引号和)，然后继续检查范围的其余部分。我从299开始，将最后两个数字固定为它们的最大值，并查找第一个数字的最大值。然后对剩下的几百个(300-999)继续这个过程，只固定最后一个数字，以300.389和390.398结束。然而，你已经可以看到它是一团糟。。。(尽管如此，我还是想把它给你，你可能会有更好的想法)
您可以立即看到的另一件事是，您的问题在索引中是对称的，所以任何有效的单元格(x，y)都会告诉您还有另一个有效单元格(y，x)。在标记方案/dfs/bfs中，可以利用这一点。