Dynamic Programming - I

public
yeskendir.sultanov Mar 31, 2024 Never 178
Clone
C++ Idp.cpp 33 lines (28 loc) | 632 Bytes
1
#include <bits/stdc++.h>
2
#define ll long long
3
4
using namespace std;
5
6
bool calced[9][9];
7
int dp[9][9];
8
9
int calc(int r, int c) {
10
if (r > 8 || r < 1 || c > 8 || c < 1) {
11
return 0;
12
}
13
if (r == 8) {
14
return 1;
15
} else if (calced[r][c]) {
16
return dp[r][c];
17
} else {
18
dp[r][c] = calc(r + 1, c - 1) + calc(r + 1, c + 1);
19
calced[r][c] = true;
20
return dp[r][c];
21
}
22
}
23
24
25
int main() {
26
std::ios_base::sync_with_stdio(false);
27
cin.tie(0);
28
cout.tie(0);
29
int col, row;
30
cin >> col >> row;
31
cout << calc(row, col);
32
return 0;
33
}