Dynamic Programming - G

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