Dynamic Programming - J

public
yeskendir.sultanov Mar 31, 2024 Never 52
Clone
C++ Jdp.cpp 32 lines (27 loc) | 646 Bytes
1
#include <bits/stdc++.h>
2
#define ll long long
3
4
using namespace std;
5
6
int n, m;
7
bool calced[51][51];
8
int dp[51][51];
9
10
int calc(int r, int c) {
11
if (r > n || r < 1 || c > m || c < 1) {
12
return 0;
13
} else if (r == n && c == m) {
14
return 1;
15
} else if (calced[r][c]) {
16
return dp[r][c];
17
} else {
18
dp[r][c] = calc(r + 2, c + 1) + calc(r + 1, c + 2);
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
cin >> n >> m;
30
cout << calc(1, 1);
31
return 0;
32
}
33
34
35
36