マトリックス・チェーンの乗算--動的計画

問題の陳述は省けて、ネット上にはたくさんあります.ダイナミックな計画と再帰について話したいです.まず再帰といえば、再帰の核心は、複雑で規模の大きい問題を、一歩一歩、問題の規模を小さくして、問題が直接解決できるようになるまで簡単にすることです.動的計画はさらに一歩近くなり、多くの問題が直接再帰されると、同じ値を何度も繰り返し計算する問題が発生することが多い.これは大きな代価である.そのため、動的計画はサブプロセスの計算結果を記録し、必要に応じて直接使用し、繰り返し計算の問題を回避し、代価を大幅に削減する.
以下はマトリクスチェーンに乗算されたコード実装であり,注釈は比較的詳細に書かれている.

#include
using namespace std;
#define LEN 5// 5     ，   0  
int main(){
    int d=1;//d      
    int r[LEN+1]={5,10,4,6,10,2};//r[i][i+1]   i       
    int c[LEN][LEN];//            ，            ，
    //             ，c[i][j]    i    j        
        for(int i=0;i0;
    }
    for(d=1;d//5   ，          4
        for(int i=0;i<=LEN-d-1;i++){
            int j=i+d;
            c[i][j]=10000;//     
            for(int k=i+1;k<=j;k++){//k       ，  ，   c[1][3],  
                    //k   2 3, 2   ，   c[1][1] c[2][3], 3   ，
                    //   c[1][2] c[3][3]
                int temp=(c[i][k-1]+c[k][j]+r[i]*r[k]*r[j+1]);
                if (temp//     
            }
        }

    }
    return c[0][4];



}