เราจะแก้โจทย์ข้อนี้ด้วย dynamic programming

ให้ $dp[n][city][a][b][c]$ แทนจำนวนวิธีในการเดินทางถ้าเซลส์แมนของเราอยู่ที่เมือง $city$ มีเวลาเหลือ $n$ วัน และเคยไปเมือง a b และ c ก็ต่อเมื่อ $a = 1$, $b = 1$, $c = 1$ ตามลำดับ มิเช่นนั้นจะเท่ากับ $0$

จะได้ว่า

โดยที่ $a', b', c'$ คือค่า $a, b, c$ ที่เปลี่ยนไปจากการไป visit เมือง $d$

สำหรับ base case เราจะให้

สำหรับ $city$ ใด ๆ $dp[0][city][a][b][c] = 1$ เมื่อ $a = b = c = 1$ มิเช่นนั้น $dp[0][city][a][b][c] = 0$

นั่นคือ เราจะลองทุก ๆ ทางที่เป็นไปได้ในการเดินออกจากเมือง $city$ และลองทุก ๆ วันในการอยู่ที่เมืองนั้นที่เป็นไปได้

ขนาดของ state-space ของ dp นี้จะเท่ากับ $\mathcal{O}(n)$ และ transition จะใช้เวลา $\mathcal{O}(n)$ ทำให้เราได้อัลกอริธึมที่จะแก้ปัญหานี้ได้ใน $\mathcal{O}(n\cdot \max(k_a, k_b, k_c))$