알고리즘
백준 13703번 물벼룩의 생존확률 C++
영춘권의달인
2023. 2. 2. 12:09
https://www.acmicpc.net/problem/13703
13703번: 물벼룩의 생존확률
수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를
www.acmicpc.net
다이나믹 프로그래밍
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int k, n;
vector<vector<int64>> cache;
int64 dp(int height, int time) {
int64& val = cache[height][time];
if (val != -1) return val;
if (height == 0) return val = 0;
if (time == 0) return val = 1;
val = 0;
return val = dp(height - 1, time - 1) + dp(height + 1, time - 1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n;
cache = vector<vector<int64>>(128, vector<int64>(128, -1));
int64 ans = dp(k, n);
cout << ans;
}