我已经被一个问题卡住了一段时间。我现在正在上算法课，但这不是一道作业题。我们还没有在课堂上学习动态规划，我只是自己做这个题。
给定一个大小为NxN的棋盘，其中每个坐标都有一个成本和另一个整数M，找到从棋盘左上角到右下角的路径的成本（只允许向右或向下移动1个方格），使得路径的总成本低于M，但尽可能接近M。 NxN和M的所有元素都是正数。
如果让我找到最小或最大路径，我可以使用标准的动态规划算法，但由于我的限制是M，我认为我必须使用另一种策略。我一直在尝试使用记忆化，并构建一个数组，其中填充了从起点到给定元素的所有可能路径的成本集合。对于(i, j)的集合，我将(i, j)的成本值添加到(i-1, j)和(j-1, i)的集合的并集中的每个元素中（如果它们存在，则只需在其位置使用集合{0}）。完成棋盘中所有元素的这个过程后，选择正确的路径就很容易了。只需选择(N, N)集合中低于M但最接近M的元素即可。
例如：
+---+---+---+
| 0 | 1 | 3 |
| 3 | 2 | 1 |
| 5 | 2 | 1 |
+---+---+---+
到给定点的路径成本:
+---+----------+----------------+
| 0 | 1 | 4 |
| 3 | 3, 5 | 4, 5, 6 |
| 8 | 5, 7, 10 | 5, 6, 7, 8, 11 |
+---+----------+----------------+
这种做法空间利用率非常低。如果我算对了，（N，N）节点集合中元素数量的最坏情况是(N+1)!/((N+1)/2)!。我是否忽略了解决此问题的更快速（时间或空间）方法？