Làm sao nhận ra một bài nên dùng Dynamic Programming?

DP phù hợp khi bài có optimal substructure và overlapping subproblems.

• Optimal substructure nghĩa là đáp án lớn được xây từ đáp án nhỏ hơn; overlapping nghĩa là cùng subproblem xuất hiện nhiều lần nếu dùng recursion brute force.
• Dấu hiệu: "số cách", "max/min cost", "longest/shortest", chọn hoặc không chọn, đi trên grid, chuỗi con.
• Flow trình bày: định nghĩa state dp[i] là gì, base case, transition, thứ tự tính, đáp án nằm ở đâu, rồi tối ưu space nếu có thể.
• Không nên nhảy vào code trước khi state rõ, vì lỗi DP thường đến từ state mơ hồ.