Topic
試題 D: 矩陣
【問題描述】
把1～2020放在2×1010的矩陣里，要求同一行中右邊的比左邊大，同一列中下邊的比上邊的大，一共有多少種方案？
答案很大，你只需要給出方案數除以2020的余數即可，
【答案提交】
這是一道結果填空題，你只需要算出結果后提交即可，
本題的結果為一個 整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
Solution
本題可以利用動態規劃的思想來解決
要求左邊的數要小
上邊的數要小
那么放置數字會有兩種情形：
從小到大放置
對于每個新的數
第一種緊挨著放在第一一行
第二種緊挨著放在第二行
直接放置在第一行中無需考慮
但是如果放在下邊第二行
前提需要上邊有數才行（合法）
所以不能出現下面個數大于上面個數的情況
那可以總結出如下規律：
將當前數放在第一行：data[i][j] += data[i - 1][j]
將當前數放在第二行：data[i][j] += data[i][j - 1]（需要判斷是否合法“不要越界”）
首先初始化為1
先選擇i，之后選擇j
確保j比i小放在同一行
同時也可以放置在下面一行
但需要保證合法不越界
在計算的同時對2020取余
最后輸出data[1010][1010]即為結果
Code
import numpy
data = numpy.zeros((1011, 1011))
data[0][0] = 1
for i in range(0, 1011):
for j in range(0, 1011):
if i > j:
data[i][j] += data[i - 1][j] % 2020
if j:
data[i][j] += data[i][j - 1] % 2020
print(data[1010][1010])
Answer
1340
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/258427.html
標籤：python