Câu hỏi của ´꒳`×͜×

Question

ai giúp mình học quy hoạch động đi mình loay hoay mãi không hiểu.
trong C++ nhé

LÊ CÔNG BAN · Accepted Answer

Nguuuu

Câu trả lời:

Nguuuu

Quoc Tran Anh Le · Answer

Quy hoạch động là cách giải bài toán lớn bằng cách chia thành nhiều bài toán nhỏ, lưu kết quả đã tính để không phải tính lại.

Cách học dễ nhất:

Bước 1. Xác định trạng thái dp
dp[i] nghĩa là đáp án tốt nhất đến vị trí i

Bước 2. Tìm công thức chuyển
dp[i] được tính từ các dp trước đó

Bước 3. Tìm điều kiện ban đầu
Ví dụ dp[0], dp[1]

Bước 4. Viết vòng lặp tính dp

Ví dụ bài Fibonacci:

f[0] = 0
f[1] = 1
f[i] = f[i - 1] + f[i - 2]

Code C++:

#include
using namespace std;

int main() {
int n;
cin >> n;

vector f(n + 1); f[0] = 0; if (n >= 1) f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } cout << f[n]; return 0;

}

Giải thích: Muốn tính f[i] thì chỉ cần biết f[i - 1] và f[i - 2], nên ta lưu các kết quả trước vào mảng f để dùng lại.