→ Khái niệm: là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau và cấu trúc con tối ưu.

→ Tác dụng: lưu kết quả của bài toán con nên khi được gọi sẽ không cần phải tính lại → làm giảm thời gian tính toán.

→ Thuật toán quy hoạch động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu.

→ Ví dụ:  bài toán tính số Fibonacci:

def fib(n):

if n <= 1:

return n

return fib(n -1) + fib(n - 2)

- Quy hoạch động :

chính là một trong số những phương pháp có thể giúp chúng ta tối ưu hóa quá trình tính toán này. Mỗi bài toán con (số fib) sẽ được lưu lại trước khi tính những bài toán con lớn hơn.

- Tác dụng: giúp việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.

- Ví dụ:

In the city, roads are arranged in a grid pattern. Each point on the grid represents a corner where two blocks meet. The points are connected by line segments which represent the various street blocks. Using the cartesian coordinate system, we can assign a pair of integers to each corner as shown below.

You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. You will return the number of distinct paths that lead to your destination. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a String[] bad describing which blocks are bad. If (quotes for clarity) "a b c d" is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let's say
width = 6
length = 6
bad = {"0 0 0 1","6 6 5 6"}
The picture below shows the grid, with untraversable blocks darkened in black. A sample path has been highlighted in red.

Examples

0)

6

6

{"0 0 0 1","6 6 5 6"}

Returns: 252

Example from above.

1)

1

1

{}

Returns: 2

Four blocks aranged in a square. Only 2 paths allowed.

2)

35

31

{}

Returns: 6406484391866534976

Big number.

3)

2

2

{"0 0 1 0", "1 2 2 2", "1 1 2 1"}

Returns: 0

Vẫn trên tư tưởng quy hoạch động, dễ thấy ta cần duyệt từ đỉnh (0,0). Số lượng đường đi đến đỉnh (i,j) sẽ dựa trên số lượng đường đi đến đỉnh (i-1,j) và đỉnh (i, j-1). Chú ý nếu đường đi từ (i-1,j) hoặc (i, j-1) đến (i,j) bị chặn thì ta sẽ không tính đoạn đường đó nữa.

Sau đây là đoạn code (C++):

#include <iostream> #include <vector> #include <string> #include <sstream> #include <cmath> #include <algorithm> using namespace std; class AvoidRoads{ public: long numWays(int width, int height, vector<string> bad); }; long AvoidRoads::numWays(int width, int height, vector<string> bad){ bool badVertical[width+1][height+1]; bool badHorizontal[width+1][height+1]; for(int i = 0; i <= width; i++){ for(int j = 0 ; j <= height; j++){ badVertical[i][j] = false; badHorizontal[i][j] = false; } } for(int i = 0; i< bad.size(); i++){ stringstream temp(bad[i]); int x, y, z, t; temp >> x >> y >> z >> t; if(abs(z - x) ==1){ badHorizontal[min(x,z)][y] = true; cout << "bad Horizontal at: " << min(x,z) << ", " << y << "\n"; } else if(abs(t - y) == 1){ badVertical[x][min(y,t)] = true; cout << "bad Vertical at: " << x << ", " << min(y,t) << "\n"; } } long res [width+1][height+1]; res[0][0] = 1; for(int i = 0; i<= width; i++ ){ for(int j = 0; j <= height; j++){ //don't override the base case if((i == 0) && (j == 0)){ continue; } long temp = 0; if(i>0 && !badHorizontal[i-1][j] ) { temp += res[i-1][j]; } if(j>0 && !badVertical[i][j-1]){ temp += res[i][j-1]; } cout << "temp = " << temp << "\n"; res[i][j] = temp; cout << "Ways to (" << i << "," << j << ") is: " << res[i][j] << "\n"; } } return res[width][height]; }