动态规划学习(1)-数字三角形问题

为了能掌握动态规划的求解方法，以后会做大量的DP题目，也会把必要的笔记记录下来。 题目:

用递归的方法是可以解决的，以D(i,j)表示第i行第j个数字（从1开始计算），想象用一个方格网将数字三角形装起来，下一步只能是D(i+1,j)或D(i+1,j+1)，递归的出口是D(1,1). 下面给出程序:

#include<iostream> using namespace std; #define MAX_NUMBER 100 int D[MAX_NUMBER][MAX_NUMBER]; int N; int MaxSum(int i, int j) { if (i == N)return D[i][j]; int Sum1 = MaxSum(i + 1, j); int Sum2 = MaxSum(i + 1, j + 1); if (Sum1 > Sum2) return Sum1 + D[i][j]; else return Sum2 + D[i][j]; } int main() { cout << "Please input the rows of numbers you want to test:" << endl; cin >> N; for (int i = 1; i <= N; i++) for (int j = 1; j <= i; j++) { cout << "row " << i << " number " << j << ":"<<endl; cin >> D[i][j]; } cout << endl; cout << "The max sum of these triangle digits is :" << MaxSum(1, 1) << endl; return 0; }

运行结果:

Please input the rows of numbers you want to test: 5 row 1 number 1: 7 .......... row 5 number 3: 2 row 5 number 4: 6 row 5 number 5: 5 The max sum of these triangle digits is :30

这个程序非常低效，原因是递归调用时调用函数次数过多，而且每次调用时都重新计算一次之前的结果，想想递归调用时的过程(想象成一个栈),每次计算MaxSum(i,j),都得计算MaxSum(i+1,j)和MaxSum(i+1,j+1)。 解决的办法是计算了MaxSum(i,j)后就记住，下次要用时直接拿出来，不用再重复计算.可以用一个二维数组记住MaxSum的值。 修改如下:

#include<iostream> #include<memory.h> using namespace std; #define MAX_NUMBER 100 int D[MAX_NUMBER][MAX_NUMBER]; int N; int MaxSumNow[MAX_NUMBER][MAX_NUMBER]; int MaxSum(int i, int j) { if (i == N)return D[i][j]; if (MaxSumNow[i + 1][j] == -1) MaxSumNow[i + 1][j] = MaxSum(i + 1, j); if (MaxSumNow[i + 1][j + 1] == -1) MaxSumNow[i + 1][j + 1] = MaxSum(i + 1, j + 1); if (MaxSumNow[i + 1][j] > MaxSumNow[i + 1][j + 1]) return MaxSumNow[i + 1][j] + D[i][j]; return MaxSumNow[i + 1][j + 1] + D[i][j]; } int main() { cout << "Please input the rows of numbers you want to test:" << endl; cin >> N; memset(MaxSumNow, -1, sizeof(MaxSumNow)); for (int i = 1; i <= N; i++) for (int j = 1; j <= i; j++) { cout << "row " << i << " number " << j << ":" << endl; cin >> D[i][j]; } cout << endl; cout << "The max sum of these triangle digits is :" << MaxSum(1, 1) << endl; return 0; }

哈哈，已经使用了动态规划啦。将一个问题分解为子问题进行解决，为避免重复计算而保存中间结果的方法就是动态规划。能使用动态规划方法求解问题的条件是:最优解的每个局部解也是最优的。