Solutions of Path with length k
Select solution language
minh2008
Created at
15 likes
Ý tưởng: sử dụng dfs từng đỉnh và dùng phương pháp quy hoạch động để tính toán.
Gọi dp[u][j] là số lượng đường đi đơn có độ dài j từ đỉnh u đến một đỉnh con bất kì của u.
-TH1: số lượng đường đi từ đỉnh u bất kì đến đỉnh v bất kì là con của đỉnh u có độ dài là k
- =sum(dp[x][k-1]) (x là một đỉnh con trực tiếp của u).
- note: nối 1 đoạn có độ dài k-1 bất kì với đỉnh u nếu giữa đoạn con đó và u có đường đi trực tiếp.
-TH2: số lượng đường đi có độ dài là k được tạo bởi 2 nhánh của 1 đỉnh u bất kì:
- =sum(dp[u][i]*dp[v][k-i-1]) (v là một đỉnh con trực tiếp của u) (1 <= i < k).
Code tham khảo: https://ideone.com/HShhg2