定义全局变量k存储子函数计算最大收益时的变量i
#include "stdafx.h"
#include <iostream> using namespace std; int k=0; int Max(int a, int b) { return a>b ? a : b; } int MEMOIZED_CUT_ROD_AUX(int p[], int n, int r[],int &k) { static int q; //int A[10]; if (r[n] >= 0) {//保存已求过的值。 return r[n]; } if (n == 0) { q = 0; } else { q = -0x7fffffff; for (int i = 0; i<n; i++) { A[i] = MEMOIZED_CUT_ROD_AUX(p, n - i - 1, r,k); // cout << A[i] << endl; if (q < (p[i] + MEMOIZED_CUT_ROD_AUX(p, n - i - 1, r,k))) { q = p[i] + MEMOIZED_CUT_ROD_AUX(p, n - i - 1, r,k); k = i; } } } r[n] = q; cout << q << endl; return q; } int MEMOIZED_CUT_ROD(int p[], int n) {//方法①自顶向下的动态规划方案 int *r = new int[n]; for (int i = 0; i<n; i++) { r[i] = -0x7fffffff; } return MEMOIZED_CUT_ROD_AUX(p, n, r,k); } int BOTTOM_UP_CUT_ROD(int p[], int n) {//方法②自底向下的动态规划方案 int *r = new int[n]; r[0] = 0; for (int j = 0; j<n; j++) { int q = -0x7fffffff; //int q=p[j+1]; for (int i = 0; i <= j; i++) { q = Max(q, p[i] + r[j - i]); } r[j + 1] = q; } return r[n]; } int _tmain(int argc, _TCHAR* argv[]) { const int n = 10; int p[10] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 }; cout << MEMOIZED_CUT_ROD(p, 9) << endl; cout << BOTTOM_UP_CUT_ROD(p, 9) << endl; cout << k << endl; return 0; }