Solving Dynamic Programming with Matrix Exponentiation
Jump to navigation
Jump to search
ตัวอย่างโจทย์
Unweighted Undirected graph หา จำนวน path ที่ length = k ให้ egde มา ทุก edge = 1 A[i][j] = 1 Example A^2 [i][j] = 10 คือ ในกราฟ A มี path จาก i ไป j ที่ length = 2 เท่ากับ 10 path A^k [i][j] = number of path that length equals 'k'
https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation
