✅ DP ✅ Top Down

質問する

リンク

に答える

1.問題のアクセスと解決ロジック（解法）

この係数の性質に基づいて、次の式を満たします.
(N,K)=(N−1,K−1)+(N−1,K)(N,K)=(N-1,K-1)+(N-1,K)(N,K)=(N−1,K−1)+(N−1,K)

同じ演算を再帰的および繰返し実行しないように注記モードを使用する->DPを用いたTop Downメソッド

NとKが同時に、この係数が1、Kが0の場合、この係数は1である.

2.コード

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int memo[1001][1001]; // memo[N][K]
int N, K;

int dp(int N, int K)
{
    if (memo[N][K] != 0) // 이미 구한 값이면 저장해놓은 값 꺼내서 리턴 (메모이제이션)
        return memo[N][K];

    if (N == K || K == 0) memo[N][K] = 1;
    else memo[N][K] = (dp(N-1,K-1) + dp(N-1,K)) % 10007;

    return memo[N][K];
}

int main()
{   
    cin >> N >> K;
    
    dp(N, K);
    
    cout << memo[N][K] << "\n";

    return 0;
}

3.時間複雑度分析

私たちはすべての状況を見つけます.
O(N)O(N)O(N)

4.問題の重要な部分

DP問題で重要なのは,点火式の導出である.
オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか