算法导论15.3 备忘录方法

本文主要是介绍算法导论15.3 备忘录方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

备忘录使动态规划的一种变形,此处用备忘录解决前面的矩阵链乘次数最少问题.
由之前的代码修改而来见该页
动态规划函数matrix_chain_order()
改为备忘录函数memoized_matrix_chain()和lookup_chain()

#include <iostream>
#include <string>
using namespace std;
static string A[7] = {"A0","A1","A2","A3","A4","A5","A6"};//六个矩阵A1～A6 但是伪码是从下标1开始计算，因此在首位填充0
static int p[7] = {30,35,15,5,10,20,25};//同上，A[1]的维数为p[0]*p[1]int lookup_chain(int **m, int ** s, int i, int j)
{if(m[i][j] < 99999)return m[i][j];if(i == j)m[i][j] = 0;else{for(int k = i; k <= j-1; k++){int q = lookup_chain(m, s, i, k) + lookup_chain(m, s, k+1, j) + p[i-1] * p[k] * p[j];if(q < m[i][j]){m[i][j] = q;s[i][j] = k;}}}return m[i][j];
}
int memorized_matrix_chain(int **m, int ** s)
{int n = sizeof(p)/sizeof(int) -1;for(int i = 1;i <= n; i++)for(int j = i; j <= n; j++)m[i][j] = 99999;return lookup_chain(m, s, 1, n);
}void print_optimal_parens(int **s, int i,int j)
{if(i == j)cout<<A[i];else{cout << "(";print_optimal_parens(s, i, s[i][j]);print_optimal_parens(s, s[i][j] + 1,  j);cout << ")";}
}int** matrixInit(int row,int col)
{int **matrix;matrix = (int**)malloc(sizeof(int*)*row);for(int i = 0 ; i < col; i++)matrix[i] = (int*)malloc(sizeof(int)*col);return matrix;
}int main() {int **s;int **m;int n = sizeof(p)/sizeof(int) -1;m = matrixInit(n+1,n+1);s = matrixInit(n+1,n+1);for(int i = 0;i<=n;i++)for(int j =0;j<=n;j++)m[i][j] = 99999;//数组赋初值int q = memorized_matrix_chain(m,s);//此处q=15125,为m[1][6]的值,也是递归函数最顶层lookup_chain(m, s, 1, 6)的返回值.print_optimal_parens(s,1,6);return 0;
}