dinamicProgramming.txt

                        TASK1

int f(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;

	return f(n - 1) + f(n - 2) + f(n - 3);
}

int vars[3];
	vars[0] = 1; vars[1] = 2; vars[2] = 4;
	int n;
	cin >> n;
	for (int i = 3; i < n; i++) {
		vars[i % 3] = vars[0] + vars[1] + vars[2];
	}
	cout << vars[(n-1)%3];
  
                        TASK2
int** matrix;
	int n, m;
	cin >> n >> m;
	matrix = new int*[n];
	for (int i = 0; i < n; i++)
		matrix[i] = new int[m];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 || j == 0) { //все клетки вида (1,y) и (x,1) имеют только один маршрут — по прямой вниз или по прямой вправо
				matrix[i][j] = 1;
			}
			else {
				matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
			}
		}
	}

	cout << matrix[n - 1][m - 1];
  
  реализация через рекурсию (НЕ ДЕЛАТЬ)
  int f(int i, int j) {
    if(i==1 || j==1) return 1;
    return f(i-1, j)+f(i, j-1);
}