algospot - snail

//algospot - snail
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<vector<double>> cache;
 
void init()
{
    cout << fixed;
    cout.precision(10);
    cin >> N >> M;
    cache = vector<vector<double>>(M, vector<double>(N, -1.0));
}
 
double dp(int day, int met)
{
    if(day == M)
        if(met >= N)
            return 1.0;
        else
            return 0.0;
 
    if(met >= N)
        return 1.0;     
 
    double& ret = cache[day][met];
    if(ret != -1.0)
        return ret;
    
    return ret = dp(day+1, met+1)*0.25 + dp(day+1, met+2)*0.75;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        cout << dp(0, 0) << "\n";
    }
}

 

 

 

 

 

 

https://algospot.com/judge/problem/read/SNAIL

algospot.com :: SNAIL

 

 

 

 

 

 

SNAIL

cache[day][met] : day번째 날에 met높이만큼 올라갈 확률

 

<점화식>

cache[day][met] = 0.25*cache[day+1][met+1] + 0.75*cache[day+1][met+2]

 

경우의수, 확률 DP 문제!

위의 문제는 경우의 수를 구하는 풀이방법과 크게 다른점이 없습니다!

경우의 수를 구하는 문제는 기저사례에서 조건을 만족할경우 return 1, 만족하지 못하면 return 0을 합니다. 확률을 계산하는 경우라면 해당 조건의 확률을 return 해야합니다.

이때 점화식에서 알수 있듯이 기저사례가 조건을 만족하는지 만족하지 않는지 확인만 하고, 해당 기저사례의 확률은 재귀함수가 반환될때 구해주어도 똑같다는것을 알수 있습니다!
(반환할때 확률을 구해주는것은 단지 곱셈의 순서를 역으로 해주는것과 같기 때문입니다.)