Quy hoạch động tìm số cách biểu diễn n thành tổng các số chính phương

[An_Pham2 (Ấn Phạm)]

Hải có một số nguyên dương n , Hải muốn biết có bao nhiêu tập hợp thỏa mãn:

• Các số trong tập hợp là các số dương và là các số chính phương.
• Không có 2 phần tử nào giống nhau.
• Tổng tất cả các phần tử bằng n .

Hai tập được gọi là khác nhau nếu chúng khác nhau về số lượng phần tử hoặc tồn tại phần tử ở tập hợp này mà tập hợp kia không có.

Ví dụ:

• Với n = 100 , thì countCase(n) = 3.
  Giải thích: 3 dãy đó là:
  • {1,9,16,25,49}
  • {36,64}
  • {100}
• Với n = 5 , thì countCase(n) = 1.

---

Cho em xin cách quy hoạch động bài này với ạ

[anon12276517]

Bài này trên codelearn à :)))
Đầu tiên là sàng vào mảng arr tất cả các số chính phương từ 1 --> n
Nhận thấy đây là tập hợp các số khác nhau ==> Cần lưu lại max của dãy để xem có bị trùng hay không

==> f[i] sẽ là mảng chứa max của các tập hợp thỏa mãn với tổng = i;

Truy hồi f[i]
Duyệt mảng arr để lấy các số chính phương square

• Nếu square = i thì thêm square vào f[i]
• Nếu i < square thì duyệt f[i - square] xem có bao nhiêu phần tử < square thì add từng đấy phần tử square vào f[i]

f[n].length sẽ là kết quả…

[Grevyalres_X (Pzanitor)]

Lọc ra các số chính phương và các số trùng nhau, biến nó thành bài toán cổ điển thôi.
https://vnoi.info/wiki/algo/dp/basic-problems#2-vali-b_2-4-một-số-bài-toán-khác_dãy-con-có-tổng-bằng-s