Thuật toán qui hoạch động (Dynamic programing)

#include <cstdio>

using namespace std;
//Xay dung ham de qui tinh so fibonacci
int fibonacci(int i){
   if (i == 1 || i == 2) return 1;
   return fibonacci(i - 1) + fibonacci(i - 2);
}

int main(){
   int n;
   scanf("%d", &n);
   printf("%d", fibonacci(n));
}

#include <cstdio>

using namespace std;

int main(){
   int n, F[100];
   //Khoi tao 2 gia tri ban dau la F[1] = 1 va F[2] = 1
   F[1] = 1;
   F[2] = 1;
   for (int i = 3; i <= 50; i++)
      F[i] = F[i - 1] + F[i - 2];//F[i] duoc xay dung tu cac sub-solution la F[i - 1] va F[i - 2]
   scanf("%d", &n);
   printf("%d", F[n]); //Cuoi cung chi can xuat so thu F[n] la xong :D
}

Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).

Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)

Input
Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.

M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải

Output
Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Example
Input:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Output:
41

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
   //Initial
   int n, m, A[105][105];
   //Input
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
         scanf("%d", &A[i][j]);
   //Process
   int dp[105][105];
   for (int i = 1; i <= n; i++) dp[i][1] = A[i][1];//Khoi tao cac gia tri ban dau
   /*Mang dp hien tai:
   9 0 0 0 0 0 0
   0 0 0 0 0 0 0
   8 0 0 0 0 0 0
   1 0 0 0 0 0 0
   7 0 0 0 0 0 0
   */
   for (int j = 2; j <= m; j++)
      for (int i = 1; i <= n; i++){
         if (i == 1) dp[i][j] = max(dp[i][j - 1], dp[i + 1][j - 1]);
         else if (i == n) dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1]);
         else dp[i][j] = max(dp[i][j - 1], max(dp[i + 1][j - 1], dp[i - 1][j - 1]));
         dp[i][j] += A[i][j];
      }
   /*Mang dp sau khi xu li
   9 7 14 16 24 27 35
   0 8 14 23 24 31 34
   8 9 16 18 28 31 36
   1 7 13 18 19 34 35
   7 5 13 15 19 22 41
   */
   int maxVal = -10000;
   for (int i = 1; i <= n; i++) maxVal = max(maxVal, dp[i][m]);
   printf("%d", maxVal);//Gia tri max la 41
}

/*Example test:
Input:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Output:
41
*/

#include <iostream>
using namespace std;
int main() {
   int n,BT = 0,bt[100];
   cout << "Nhap so nguoi:";
   cin >> n;
   cout << "Nhap thoi gian tung nguoi:\n";
   for (int i = 0;i < n;i++)
      cin >> bt[i];
   int min = bt[0];
   for (int i = 0;i < n;i++)
      if (bt[i] > bt[i + 1])
         min = bt[i + 1];
   for (int i = 0;i < n;i++)
      if (bt[i] != min)   
         BT += bt[i];
      else   
         BT += min * (n - 2);      
   cout << "KQ: " << BT << "\n";
}