技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

目次

基本的な内容:

動的プログラミング:

動的プログラミングを理解する上での問題が紹介されます。

分析: (暴力的な後戻り)

コード例:

残忍な捜索:

DFS コード例: (検索)

ブルートフォース再帰によって生成された再帰ツリー:

メモ化された検索:

コード例:

動的プログラミング:

コード例: (動的プログラミング、最小の部分問題から開始)

実行プロセス (動的プログラミング):

分析：（動的計画法）

スペースの最適化:

コード例:

分析：

---

基本的な内容:

動的計画法とは何か、動的計画法が手段としてどのような問題を解決できるか、動的計画法の分類、および特定の分類によって解決できる特定の問題の分類。

動的プログラミング:

これは、問題を一連の小さなサブ問題に分解し、サブ問題の解を保存することで計算の繰り返しを回避し、時間効率を大幅に向上させる重要なアルゴリズム パラダイムです。

動的プログラミングを理解する上での問題が紹介されます。

この問題は、合計 n 段の階段があるとすると、各段で 1 段または 2 段ずつ上がることができ、建物の頂上まで登る選択肢は何通りありますか。

分析: (暴力的な後戻り)

この質問の目的は、解の数を見つけることです。バックトラックすることであらゆる可能性を徹底的に網羅することを検討できます。 。具体的には、複数ラウンドの選択プロセスとして階段を登ることを想像してください。地面から開始して、ラウンドごとに 1 つまたは 2 つの段を選択し、階段の頂上に到達するたびに選択肢の数に 1 を加え、階段の頂上に到達するたびに選択肢の数を増やします。プルーンの頂上に到着します。

コード例：

# python代码示例
def backrack(choices,state,n,res) :
    if state == n :
        res[0] += 1 
    for choice in choices :
        if state + choice > n :
            continue
        backrack(choices,state+choice,n,res)
def climbing_stairs_backrack(n) :
    choices = [1,2]
    state = 0
    res = [0]
    backrack(choices,state,n,res)
    return res[0]
n = int(input())
print(climbing_stairs_backrack(n))

// c++代码示例
void backrack(vector<int> &choices, int state, int n, vector<int> &res)
{
    if (state == n )
    {
        res[0]++ ;
    }
    for (auto &choice : choices)
    {
        if (state + choice > n)
        {
            continue ;
        }
        backrack(choices, state + choice, n, res)
    }
}
 
int climbingStairsBackrack(int n)
{    
    vector<int> choices = {1 , 2 } ;
    int state = 0 ;
    vector<int> res = [0] ;
    backrack(choices, state, n, res) ;
    return res[0] ;
}

残忍な捜索:

バックトラッキング アルゴリズムは通常、問題を明示的に分解するのではなく、問題を一連の意思決定ステップとして扱い、ヒューリスティックと枝刈りを通じて可能なすべての解決策を検索します。

問題分解の観点からこの質問を分析してみることができます。 i 番目のレベルに到達するための dp[i] 解があると仮定すると、dp[i] が元の問題であり、その副次問題は次のとおりです。

dp[i-1]，dp[i-2]，dp[1]，dp[2]

各ラウンドで 1 段か 2 段しか上がらないので、i 番目の階段に立つとき、前のラウンドでは i-1 または i-2 の段にしか立つことができません。言い換えれば、i-1 番目または i-2 番目のレベルから i 番目のレベルにのみ移動できます。

このことから、重要な推論を導き出すことができます。i-1 番目のレベルまで上がった計画の数と i-2 番目のレベルまで上がった計画の数を足したものは、i 番目のレベルまで上がった計画の数に等しいということです。 - 番目のレベル。式は次のとおりです。

dp[i] = dp[i-1] + dp[i-2]

これは、建物の登りの問題には再帰的な関係があり、部分問題の解を構築することで元の問題を解決できることを意味します。

DFS コード例: (検索)

# python 代码示例
def dfs(i : int) -> int :
    if i == 1 or i == 2 :
        return i
    count = dfs(i - 1) + dfs(i - 2)
    return count
def climbing_stairs_dfs(n : int) -> int :
    retunr dfs(n)

// c++ 代码示例
int dfs(int i)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    int count = dfs(i - 1) + dfs(i - 2);
    return count ;
}
int climbingStairsDFS(int n)
{
    retunr dfs(n) ;
}

激しい再帰によって生成された再帰ツリー：

再帰ツリーにおける上述の重複問題を解決するには、メモリ探索法を使用して、繰り返し構築される多数の同一のサブツリーを除去し、それによって計算効率を向上させることができる。 (重複する部分問題）

メモ化された検索:

重複するすべての部分問題を 1 回だけ計算するには、配列 nem を宣言して各部分問題の解を記録し、検索プロセス中に重複する部分問題を取り除く必要があります。

1. dp[i] が初めて計算されると、以降の使用のために nem[i] に記録されます。
2. dp[i] が再度計算されるときは、部分問題の繰り返し計算を避けるために、結果が nem[i] で直接取得されます。

コード例:

# python 代码示例
def dfs(i : int, mem : list[int]) -> int :
    if i == 1 or i == 2 :
        return i
    if mem[i] != -1 :
        return mem[i]
    count = dfs(i - 1, mem) + dfs(i - 2, mem)
    # 记录dfs(i)
    mem[i] = count
    return count
def climbing_stairs_dfs_mem(n : int) -> int :
    mem = [-1] * (n + 1)
    return dfs(n, mem)

// c++ 代码示例
int dfs(int i, vector<int> &mem)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    if (mem != -1)
    {
        return mem[i] ;
    }
    int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
    mem[i] = count ;
    return count ;
}
int climbingStairsDFSMem(int n)
{
    vector<int> mem(n + 1, -1) ;
    return dfs(n, mem) ; 
}

メモ化後、すべての重複する部分問題は 1 回だけ計算され、時間計算量は O(n) に最適化されます。

動的プログラミング:

メモ化された検索は、元の問題 (ルート ノード) から開始して、既知の最小のサブ問題 (リーフ ノード) を解決するまで、より大きなサブ問題をより小さなサブ問題に再帰的に分解します。 。その後、バックトラッキングによってサブ問題の解決策が層ごとに収集され、元の問題の解決策が構築されます。

対照的に、動的プログラミングは「下から上へ」のアプローチです。つまり、最小の部分問題の解決策から始めて、元の問題の解決策が得られるまで、より大きな部分問題の解決策を繰り返し構築します。

動的プログラミングには後戻り処理が含まれないため、再帰を使用せずにループ反復を使用して実装するだけで済みます。

コード例: (動的プログラミング、最小の部分問題から開始)

# python 代码示例
def clibing_stairs_dp(n) :
    if n == 1 or n == 2 :
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3,n + 1) :
        dp[i] = dp[i-1] + dp[i- 2]
    return dp[n]

// c++ 代码示例
 
int climbingStairsDP(int n) 
{
    if (n == 1 || n == 2)
    {
        retunr n ;
    }
    vector<int> dp(n + 1, -1) ;
    dp[1] = 1 ;    
    dp[2] = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + dp[i- 2] ;
    }
    return dp[n] ;
}

実行プロセス (動的プログラミング):

分析：（動的計画法）

バックトラッキング アルゴリズムと同様に、動的プログラミングでも「状態」の概念を使用して、問題解決の特定の段階を表します。各状態は部分問題と、対応する局所最適解に対応します。例: 階段を登る問題のステータスは、現在の階段の次数 i として定義されます。

上記に基づいて、動的用語の一般的な用語を要約できます。

1. 配列 dp は {dp table} と呼ばれ、dp[i] は状態 i に対応する部分問題の解を表します。
2. 最小の部分問題 (1 番目と 2 番目の階段) に対応する状態を初期状態と呼びます
3. 再帰式 dp[i] = dp[i-1] + dp[i-2] は状態方程式と呼ばれます

スペースの最適化:

dp[i] は dp[i-1] と dp[i-2] にのみ関連します

配列を使用してすべての部分問題の解を保存する代わりに、前方にスクロールするために必要な変数は 2 つだけです。

コード例:

# python 代码示例
def clibing_stairs_dp_comp(n) :
    if n == 1 or n == 2 :
        return n
    a, b = 1, 2
    for _ in range(3, n + 1) :
        a, b = b , a + b
    return b

// c++ 代码示例
int climbingStairsComp(int n) 
{
    if (n == 1 || n == 2)
    {
        return n ;
    }
    int a = 1 , b = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        int temp = b ;
        b = a + b ;
        a = temp ;
    }
    return b ;
}

分析：

配列 dp が占有する空間が省略され、空間の複雑さが O(n) から O(1) に軽減されます。

動的計画法の問題では、現在の状態は限られた数の前の状態にのみ関連します。現時点では、必要な状態のみを保持し、「次元削減」を通じてメモリ空間を節約できます。 。このスペース最適化手法は、「ローリング変数」または「ローリング配列」と呼ばれます。