Giả sử có hai người chơi đang chơi trò lật kèo. Ở đây chúng ta có một chuỗi chỉ chứa hai ký tự sau:+ và -, player1 và player2 thay phiên nhau lật hai ký tự "++" liên tiếp thành "-". Trò chơi kết thúc khi một người chơi không thể di chuyển được nữa và do đó người còn lại sẽ là người chiến thắng. Chúng tôi phải xác định một chức năng để kiểm tra xem liệu người chơi bắt đầu có thể đảm bảo chiến thắng hay không.
Vì vậy, nếu đầu vào là s ="++++", thì đầu ra sẽ là true, vì người chơi bắt đầu có thể đảm bảo chiến thắng bằng cách lật "++" ở giữa để trở thành "+ - +".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản ghi nhớ bản đồ
-
Xác định một hàm giải quyết (), điều này sẽ mất s,
-
nếu có trong bản ghi nhớ, thì -
-
trả lại [s] thư báo
-
-
có thể:=false
-
n:=kích thước của s
-
để khởi tạo i:=0, khi tôi
-
nếu s [i] giống với '+' và s [i + 1] giống với '+', thì -
-
s [i]:='-', s [i + 1]:='-'
-
có thể:=có thể HOẶC nghịch đảo của (các) giải quyết
-
s [i]:='+', s [i + 1]:='+'
-
nếu có thể là khác 0, thì -
-
trả lại bản ghi nhớ [s]:=có thể
-
-
-
-
trả lại bản ghi nhớ [s]:=có thể
-
Từ phương thức chính, hãy làm như sau -
-
trả về (các) giải pháp
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
unordered_map <string, bool> memo;
bool solve(string s){
if (memo.count(s))
return memo[s];
bool possible = false;
int n = s.size();
for (int i = 0; i < n - 1; i++) {
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = '-';
s[i + 1] = '-';
possible |= !solve(s);
s[i] = '+';
s[i + 1] = '+';
if (possible)
return memo[s] = possible;
}
}
return memo[s] = possible;
}
bool canWin(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.canWin("++++"));
} Đầu vào
"++++"
Đầu ra
1