x
- Tạo bởi LQDuy
- Start date
FanBrando
Lỗ đýt gợi cảm
Em sofm giờ nghỉ stream LOL qua học code àMình đang cố gắng giải bài này https://leetcode.com/problems/coin-change-ii/ theo backtracking.
Hiện tại mình thấy logic của mình đang chạy backtracking ổn theo mình nghĩ. Tuy nhiên, có một yếu tố yêu cầu đề bài mà nó không đáp ứng được. Cụ thể: giả sử có 5 đồng, và coin là [1,2], nó không nhận ra được các trường hợp dưới đây là như nhau: 1+1+1+2 và 1+2+1+1
Mình muốn nhờ các bạn giúp dùm cách để sửa backtracking logic để giải được bài này.
Đây là logic mà mình implement backtracking.
1) mổi node có 1 state variable là remainingAmount.
2) để đi giữa các branch trong cùng hàng/level của tree, thì mình dùng for loop, đi qua lần lượt các coin.
3) để đi xuống dưới node child thì dùng recursive call, bỏ vào index của coin cho lần tới, và số tiền còn lại.
a) mình tính trước số tiền còn lại rồi mới gọi recursive function. Do đó chỉ đi tiếp xuống level thấp hơn nếu remaining>=0.
4) back tracking được thực hiện khi recursive function trả về kết quả.
a) node con chỉ trả về kết quả = 1 khi remainingAmount=0
b) value của mỗi state là ans. Được cộng với kết quả của node con.
c) khi backtracking, mình thêm một thủ thuật để reset remainingAmount.
Thực hiện với test mẫu là [1,2,5] thì mình expect kết quả là 9, logic của mình chạy ra đúng kết quả.
Tuy nhiên, mình cần thêm logic để loại bỏ trường hợp lặp lại thì mới đúng kết quả của đề bài.
Mình muốn nhờ các bạn giúp xử lý logic này.
thienanngulon
Hạt giống tầm thần
dùng cu cặc vú Lồn giải quyết nhé, đây là xam
Vjpprovv
Xàm 0 Lít
Nhìn mặt quen vl, trước làm tiktok à?
Vjpprovv
Xàm 0 Lít
Avt giống ông nào làm content về các trường dạy IT vleu
ChimToDongTimor
Thích phó đà
Mấy bài mà cách viết đề của nó cứ rối rắm như này thật khó chịu, y chang mấy bài của cái trang luyện code VN mà quên tên rồi ấy. Đề của HackerRank nó gần gũi với ngôn ngữ tự nhiên hơn
LQDuy
Người phá đò sông Đà
T bỏ qua Code lâu rồi mà tml.Em sofm giờ nghỉ stream LOL qua học code à