Bài tập quy hoạch động

[Bill_Lee]

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

[AI_Android]

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)

[Bill_Lee]

tks bạn nhé

[Gio (Gió)]

@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.

• chữ số đầu tiên có K-1 cách chọn
• các chữ số tiếp theo có K cách chọn
  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)

[Bill_Lee]

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

[Gio (Gió)]

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:

a=[[0,1],[k-1,k-1]]
b=a^n
answer=b[1][1]

[Tran_Son_Tung (Trần Sơn Tùng)]

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??