再帰とダイナミックプランニングの関係

再帰とダイナミックプランニングの関係
実は再帰はダイナミックプランニングと密接な関係があり、一般的に再帰はダイナミックプランニングに変換できます.この問題は一般的な再帰的な成果から説明できる.
まず、問題は分解することができて、多くの重なり合ったサブ問題に分解してやっと解くことができて、動態計画もこの構想で、はっきり言って動態計画は実は記憶化しました
再帰プログラム動的計画は多くの再帰問題の解を格納し,これにより多くのサブ問題の解を求めることを省き,迅速な解の目的を達成した.
再帰は実は上から下へ解くので、よくある再帰の形式は

dfs(int n){
  if(n == ?)
   return 
  dfs(n-1)
}

は上部から下へ反復している.これは動的計画とは逆に、動的計画の構想は常に下から上へ一般的な形式である.

dp[n][n];
dp[0][0] = ?;
dp[1][0] = ?
for(int i = 1; i < n; i++){
   for(int j = i; j < n; j++){
  dp[i][j] = max(dp[i - 1][j], dp[i][j-1]) + ?
}
}

の2つの形式は逆ですが、問題を解決する形式は同じで、いずれも最後のレイヤを反復し続け、再帰はより多くのスタックが一時的なデータを格納しているにすぎません.
具体的な問題はアルゴリズム導論の動的計画を見ることができ,鋼管の例を分けることができる.
以下にleetcodeの例70を示す.Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

動的計画アプローチ:

class Solution {
    int res = 0;
    int[] dp;
    public int climbStairs(int n) {
        if(n == 1 || n == 0)
            return 1;
        dp = new int[n+5];
        dp[0] = 1;
        dp[1] = 1;  
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] ;
        }
        res = dp[n];
        return res;
        
    }
}

再帰的アプローチ:

class Solution {
private:
    vector memo;

    int calcWays(int n){

        if( n == 0 || n == 1)
            return 1;

        if( memo[n] == -1 )
            memo[n] = calcWays(n-1) + calcWays(n-2);

        return memo[n];
    }
public:
    int climbStairs(int n) {

        memo = vector(n+1,-1);／／     
        return calcWays(n);
    }
};