# Quy hoạch động
## Bài toán Balo
### Đề bài
Có $n$ món đồ, mỗi món có khối lượng $w_i$ và giá trị $v_i$. Hãy chọn ra một số món đồ để xếp vào một cái balo có thể chứa khối lượng tối đa là $W$ sao cho có tổng giá trị cao nhất.
### Nhận xét
Món đồ lựa vào balo phụ thuộc 2 yếu tố: số vật được xét và khối lượng các vật. Vậy nên ta có bảng phương án 2 chiều.
### Cài đặt

for (int i=0;i<n;i++){
    for (int j=0;j<=W;j++){
        if (w[i]<=j){
            f[i][j]=max(f[i-1][j],v[i]+f[i-1][j-w[i]]);
        }
        else{
            f[i][j]=f[i-1][j];
        }
    }
}

## Bài toán dãy con đơn điệu dài nhất
### Đề bài
Cho dãy $a_1, a_2, ..., a_n$. Tìm dãy con tăng có nhiều phần tử nhất.
### Nhận xét
Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên ta có bảng phương án 1 chiều.
### Cài đặt

for (int i=0;i<n;i++){
    f[i]=1;
    for (int j=0;j<i;j++){
        if (a[i]>a[j]){
            f[i]=max(f[i],f[j]+1);
        }
    }
}