30/09/2018, 21:05
Bài tập quy hoạch động
Xin chào mọi người
em có một bài toán như thế này:
Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example:
- 1010230 is a valid 7-digit number;
- 1000198 is not a valid number;
- 0001235 is not a 7-digit number, it is a 4-digit number.
Given two numbers N and K, you are to calculate an amount of valid K based numbers, containing N digits.
You may assume that 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.
Input
The numbers N and K in decimal notation separated by the line break.
Output
The result in decimal notation.
Sample
input:
2
10
output: 90
em muốn giải bài này bằng thuật toán quy hoạch động nhưng không có ý tưởng nào cả. mọi người cho em xin chút ý tưởng với
em cảm ơn trước
Bài liên quan
F[i][0] là số cách tạo số k based có i chữ số kết thúc bằng 0
F[i][1] là số cách tạo số k based có i chữ số kết thúc khác không
F[i][0]=F[i-1][1]
F[i][1]=( F[i-1][0]+F[i-1][1] ) *(k-1)
tks bạn nhé
@AI_Android là trùm qhd rồi!
Bài này theo mình nghĩ không cần phải quy hoạch động. Có thể đếm theo cách thông thường.
Vì các bước chọn độc lập nên số các số thoã mãn là
(K-1)*K^(N-1)tại mình đang luyện thêm về qhd mà công thức của bạn đúng với trường hợp N=2 à
vì N=3 K=10 output sẽ là 891
Lúc nãy đọc thiếu chỗ 2 số 0 liền nhau. Từ công thức truy hồi có thể tính được bằng nhân ma trận:
cho mình hỏi là two successive zeros nghĩa là ntn vậy? nghĩa là 2 chữ số 0 đứng cạnh nhau??