问题
给出一个数组，求不相邻的数之和最大
递推式
代码
//求不相邻的最大数之和 #include <iostream> using namespace std; #define max(a,b) (a > b ? a : b) int arr[] = {1, 2, 4, 1, 7, 8, 3}; //递归求解 int rec_opt(int i) { if(i == 0) { return arr[0]; } else if(i == 1) { return max(arr[0], arr[1]); } else { int A = arr[i] + rec_opt(i -2); int B = rec_opt(i - 1); return max(A, B); } } //非递归求解 int dp_opt() { int len_arr = sizeof(arr) / sizeof(int); //此数组用存放最大值的 int *opt = new int[len_arr]; opt[0] = arr[0]; opt[1] = max(arr[0], arr[1]); for(int i = 2; i < len_arr; i++) { int A = opt[i - 2] + arr[i]; int B = opt[i - 1]; opt[i] = max(A, B); } return opt[len_arr - 1]; } int main() { cout << rec_opt(6) << endl; cout << dp_opt() << endl; return 0; }
转载于:https://www.cnblogs.com/Gzu_zb/p/11398276.html
相关资源：JAVA上百实例源码以及开源项目