手机网站在后台怎么做编辑,深圳做h5网站设计,东莞网站关键词优化公司,南昌企业网站建设费用题目方案1#xff1a;递归方案二#xff1a;递推 题目
数字三角形问题。有一个由非负整数组成的三角形#xff0c;第一行只有一个数#xff0c;除了最下行 之外每个数的左下方和右下方各有一个数 从第一行的数开始#xff0c;每次可以往左下或右下走一格#xff0c;直…题目方案1递归方案二递推 题目
数字三角形问题。有一个由非负整数组成的三角形第一行只有一个数除了最下行 之外每个数的左下方和右下方各有一个数 从第一行的数开始每次可以往左下或右下走一格直到走到最下行把沿途经过的数 全部加起来。如何走才能使得这个和尽量大
具体实现代码中的d我们用maxsum表示 最初的位置我们用d存
1.把当前的位置(i, j)看成一个状态 然后定义状态(i, j)的指标函数d(i, j)为从格子(i, j)出发时能得到的最大和 包括格子(i, j)本身的值。在这个状态定义下原问题的解是d(1, 1)。 2.不同状态之间是如何转移的。从格子(i, j)出发有两种决策。如果往左走则走 到(i1, j)后需要求“从(i1, j)出发后能得到的最大和”这一问题即d(i1, j)。类似地往右走之后需要求解d(i 1 , j1)。由于可以在这两个决策中自由选择所以应选择d(i1,j) 和d(i1,j1)中较大的一个。 3.状态转移方程d(i,j)a(i,j)max{d(i1,j),d(i1,j1)} 4.如果往左走那么最好情况等于(i, j)格子里的值a(i, j)与“从(i1, j)出发的最大总和”之 和注意这里的“最大”二字。如果连“从(i1,j)出发走到底部”这部分的和都不是最大 的加上a(i, j)之后肯定也不是最大的。这个性质称为最优子结构optimal substructure 也可以描述成“全局最优解包含局部最优解”。 5.状态和状态转移方程一起完整地描 述了具体的算法。
方案1递归
可以用记忆化搜索的方法计算状 态转移方程。当采用记忆化搜索时不必事先确 定各状态的计算顺序但需要记录每个状态“是 否已经计算过”。 题目中说各个数都是非 负的因此如果已经计算过某个d[i][j]则它应是非负的。这样只需把所有d初始化为 1即可通过判断是否d[i][j]-1得知它是否已经被计算过。
#includeiostream
#includealgorithm
#includecmath
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int maxsum[maxx][maxx];
int ms(int i,int j);
int main()
{int i,j;cinn;for(i1;in;i)for(j1;ji;j){cind[i][j];maxsum[i][j]-1;}coutms(1,1)endl;} int ms(int i,int j)
{if(maxsum[i][j]!-1)return maxsum[i][j];//保存算过的 赋值语句本身有返回值”的规定//可以把maxsum[i][j]的工作合并到函数的返回语句中。if(in)maxsum[i][j]d[i][j];else {int yms(i1,j1);int xms(i1,j);maxsum[i][j]max(x,y)d[i][j];}return maxsum[i][j];
}
方案二递推
i是 逆序枚举 的因此在计算d[i][j]前它所需要的d[i1][j]和d[i1][j1]一定已经计算出来了。
最底下的元素dij的maxsum[i][j]一定是他自身 这样我们可以自下而上地推出每一个dij的maxsum
#includeiostream
#includealgorithm
#includecmath
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int maxsum[maxx][maxx];int main()
{int i,j;cinn;for(i1;in;i)for(j1;ji;j){cind[i][j];}for(i1;in;i)maxsum[n][i]d[n][i];for(in-1;i1;--i)for(j1;ji;j)maxsum[i][j]max(maxsum[i1][j],maxsum[i1][j1])d[i][j];coutmaxsum[1][1]endl;} 用一维数组存
//直接用d的第n行代替
#includeiostream
#includealgorithm
#includecmath
using namespace std;
#define maxx 101
int d [maxx][maxx];
int n;
int *maxsum;int main()
{int i,j;cinn;for(i1;in;i)for(j1;ji;j){cind[i][j];}maxsumd[n];for(in-1;i1;--i)for(j1;ji;j)maxsum[j]max(maxsum[j],maxsum[j1])d[i][j];coutmaxsum[1]endl;}
