数字三角形 动态规划 C++

发布于:2021-10-21 16:20:52

数字三角形

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或者右下走。只需要求出这个最大和即可,不必给出具体路径。

三角形行数大于1小于等于100,数字为0-99

直接递归的话时间复杂度太大,这里面有很多重复计算的点,所以创建一个和三角形一样大的二维数组,每当计算过这个点时就把值赋给这个数组。


#include
#include
#include
using namespace std;
#define MAX 101
int D[MAX][MAX];//存放三角形的数组
int n;
int maxSum[MAX][MAX]; //dp数组,用来记录已经算过的数

int MaxSum(int i, int j) {
if (maxSum[i][j] != -1) //如果maxSum中的值被修改过,意味着这个点已经被计算过,直接返回值就行了
return maxSum[i][j];
if (i == n)maxSum[i][j] = D[i][j];//如果到了底层,就返回自身
else {
int x = MaxSum(i + 1, j);//这是选择左下方的点
int y = MaxSum(i + 1, j + 1);//右下方的点
maxSum[i][j] = max(x, y) + D[i][j];//选择两个点中较大的加上现在所在的点
}
return maxSum[i][j];//返回计算过后的点
}


int main() {
memset(maxSum, -1, sizeof(maxSum));
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> D[i][j];
cout << MaxSum(1, 1) << endl;
}

下面是递推式

#include
#include
using namespace std;
int n;
int D[101][101];
int res[101][101] = {0};
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> D[i][j];
for (int i = 1; i <= n; i++)//把最后一行赋给res
res[n][i] = D[n][i];
//递推式,每次从下面一行选取较大的数与现在的相加
//res[i][j] = D[i][j] + max(res[i+1][j],res[i+1][j+1]);
for (int i = n - 1; i >= 1; i--)
for (int j = 1; j <= i; j++) { //j可以取到i,因为这是res是上一行了
res[i][j] = D[i][j] + max(res[i + 1][j], res[i + 1][j + 1]);
}
cout << res[1][1] << endl;
}

相关推荐

最新更新

猜你喜欢