具有整數值的矩陣的數量

Question

我必須找到左上角條目中包含1的NXM矩​​陣的數量，所有條目都是整數值，並且相鄰條目最多相差1，因爲知道N最多爲5，M可以高達10^9。很明顯，回溯算法速度不夠快，我認爲這個問題可以用矩陣求冪來解決，但是我沒有任何意義。 在此先感謝！

Answer 1

每一行是按以下形式：

x (y=x+1/x/x-1) (z=y+1/y/y-1) ... 

x的值並不重要，所以（對於N = 5）有3^4 = 81的可能性的每一行。

從這裏你可以編寫一個簡單的程序來確定哪些可能性出現在當前行的這81種可能性中的每一種的下一行中。

從那裏你應該能夠找出一個公式，如果有一個簡單的公式，否則你有一個O（10^9）算法，這至少比你開始的算法更好。

「最多」和「可以上去」確實有點亂用算法。