做电商讲师课程的网站,centos。wordpress,本地网站开发环境搭建,网站建设全程揭秘光盘文件题目#xff1a;如下图是一个数塔#xff0c;从顶部出发在每一个节点可以选择向左或者向右走#xff0c;一直走到底层#xff0c;要求找出一条路径#xff0c;使得路径上的数字之和最大#xff0c;及路径情况。(使用蛮力算法和动态规划算法分别实现#xff09; #include…题目如下图是一个数塔从顶部出发在每一个节点可以选择向左或者向右走一直走到底层要求找出一条路径使得路径上的数字之和最大及路径情况。(使用蛮力算法和动态规划算法分别实现 #includebits/stdc.h
#define MAX_SIZE 100
using namespace std;
//蛮力算法
int maxPathSumForce(int pyramid[][MAX_SIZE],int row){if(row1){return pyramid[0][0];}int maxSumpyramid[0][0];for(int i1;irow;i){for(int j0;ji;j){if(j0){pyramid[i][j]pyramid[i-1][j]; }else if(ji){pyramid[i][j]pyramid[i-1][j-1];}else{pyramid[i][j] (pyramid[i - 1][j - 1] pyramid[i - 1][j] ? pyramid[i - 1][j - 1] : pyramid[i - 1][j]);}if (pyramid[i][j] maxSum) {maxSum pyramid[i][j];}
}}return maxSum;
} //动态规划算法int maxPathSumDP(int pyramid[][MAX_SIZE], int rows) {if (rows 1) {return pyramid[0][0];}for (int i rows - 2; i 0; i--) {for (int j 0; j i; j) {pyramid[i][j] (pyramid[i 1][j] pyramid[i 1][j 1] ? pyramid[i 1][j] : pyramid[i 1][j 1]);}}return pyramid[0][0];
}signed main()
{int pyramid[MAX_SIZE][MAX_SIZE];int row,num;cout请输入数塔的层数;cinrow;cout请输入数塔的数字每层从左到右依次输入endl;for(int i0;irow;i){for(int j0;ji;j){cinnum;pyramid[i][j]num;}}cout蛮力算法最大路径和为maxPathSumForce(pyramid,row)endl;cout动态规划算法最大路径和为maxPathSumDP(pyramid,row)endl; }
蛮力算法的解释 1. 首先如果金字塔只有一行(rows 1)则直接返回金字塔顶部的值(pyramid[0][0])。 2. 初始化最大路径和为金字塔顶部的值(maxSum pyramid[0][0])。 3. 使用两个嵌套的循环遍历金字塔的每一行和每一列。外层循环变量i表示行数内层循环变量j表示列数。 4. 在内层循环中根据当前位置的行数和列数计算当前位置的值。具体计算方式如下 - 如果当前位置是行的开头(j 0)则当前位置的值等于上一行同列位置的值加上当前位置的值(pyramid[i][j] pyramid[i - 1][j])。 - 如果当前位置是行的末尾(j i)则当前位置的值等于上一行前一列位置的值加上当前位置的值(pyramid[i][j] pyramid[i - 1][j - 1])。 - 否则当前位置的值等于上一行前一列位置的值和上一行同列位置的值中的较大值(pyramid[i][j] (pyramid[i - 1][j - 1] pyramid[i - 1][j] ? pyramid[i - 1][j - 1] : pyramid[i - 1][j]))。 5. 在内层循环中每次更新当前位置的值后判断当前位置的值是否大于最大路径和(maxSum)。如果是则更新最大路径和为当前位置的值。动态规划算法的解释从下到上代码更加简洁可能性更小 1. 首先如果金字塔只有一行(rows 1)则直接返回金字塔顶部的值(pyramid[0][0])。 2. 使用两个嵌套的循环从倒数第二行开始向上遍历金字塔的每一行和每一列。外层循环变量i表示行数内层循环变量j表示列数。 3. 在内层循环中根据当前位置的行数和列数计算当前位置的值。具体计算方式如下 - 当前位置的值等于当前位置的值加上 下一行同列位置和下一行下一列位置中的较大值(pyramid[i][j] (pyramid[i 1][j] pyramid[i 1][j 1] ? pyramid[i 1][j] : pyramid[i 1][j 1]))。 4. 循环结束后金字塔顶部的值即为从顶部到底部的最大路径和。 5. 返回金字塔顶部的值。
