Tìm tất cả số nguyên không âm độ dài N sao cho hiệu tuyệt đối giữa hai chữ số liên tiếp bằng K. Không cho phép số 0 dẫn đầu (trừ số 0). Trả về theo thứ tự bất kỳ.
Ví dụ: N=3, K=7 → [181,292,707,818,929] (070 không hợp lệ).
Giải pháp DP:
dp[i] lưu các số độ dài i thỏa mãn
Khởi tạo dp[1] = {1..9}
Với i từ 1 đến N-1:
Duyệt x trong dp[i], lấy chữ số cuối lastNum
Thử digit = lastNum + K và lastNum - K (nếu 0-9)
Thêm x*10 + digit vào dp[i+1] (dùng set visited tránh trùng)Nếu N=1, thêm 0 vào dp[N]
Trả về dp[N]
Ví dụ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<int> v){ cout << "["; for(int i=0;i<v.size();i++) cout << v[i] << ", "; cout << "]"<<endl; } class Solution { public: vector<int> numsSameConsecDiff(int N, int K) { vector <int> dp[N + 1]; for(int i = 1; i <= 9; i++) dp[1].push_back(i); for(int i = 1; i < N; i++){ set <int> visited; for(int j = 0; j < dp[i].size(); j++){ int x = dp[i][j], lastNum = x % 10; int digit = lastNum + K; if(digit >= 0 && digit <= 9 && !visited.count(x*10+digit)){ dp[i+1].push_back(x*10+digit); visited.insert(x*10+digit); } digit = lastNum - K; if(digit >= 0 && digit <= 9 && !visited.count(x*10+digit)){ dp[i+1].push_back(x*10+digit); visited.insert(x*10+digit); } } } if(N == 1) dp[N].push_back(0); return dp[N]; } }; int main(){ Solution ob; print_vector(ob.numsSameConsecDiff(3,7)); }Đầu vào
3 7
Đầu ra
[181,292,707,818,929]