一个小算法，请教大家
有一个N×N方阵，现从左上角到右下角找一条路径，要求路径中各数字和最大。
条件如下：
1.N<=100。
2.路径行走方向只能向下和向右。
3.输入数据中第一行是N，接下是N行，每行N个正整数。
4.输出是最大路径最大值。
样例输入：
4
1 2 3 4
1 1 1 5
1 1 1 6
1 1 1 7
样例输出：
28
[解决办法]
路过沙发帮顶
[解决办法]
动态规划？
建一个表，纪录左上角到当前点的最大距离（当前点值+左上角节点到左节点最大距离 与 当前点值+左上角节点到上节点最大距离 的较大者）
[解决办法]
- C/C++ code
#include <iostream>using namespace std;int n,max,map[105][105];int dir[2][2]={0,1,1,0}; //控制方向void dfs(int di,int dj,int count){ if(di > n || di < 1 || dj > n || dj < 1 )return; //如果越界，返回 count += map[di][dj]; // 累加当前 路径的值 if(count > max ) max = count; if(di==n && dj == n) return ; for(int i=0;i<2;i++) { dfs(di+dir[i][0],dj+dir[i][1],count); dfs(di+dir[i][0],dj+dir[i][1],count); }}int main(){ while(cin >> n) { int i,j; for(i=1;i<=n;i++ ) { for(j=1;j<=n;j++) { cin >> map[i][j]; } } dfs(1,1,0); cout << max << endl; max = 0; } return 0; }
[解决办法]
矩阵从左往右，从上向下标号
1,4是节点2，1的下标
result = 1+ max{distance(1，15)+distance(4，15)}
类似这样递归下去，到distance(15，15)时终止
[解决办法]
用C帮你实现下：
#include<stdio.h>
void main()
{
inti,j,n,a[100][100],sum;
scanf("%d",&n);//输入阶数
for(i=0;i<n;i++)//读入数组
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
i=j=0;
sum=a[i][j];//初值为第一个元素
while(a[i][j]!=a[n-1][n-1])
{
if(a[i+1][j]>=a[i][j+1] && i<n && j<n)//向下
{
sum+=a[i+1][j];i++;continue;
}
if(a[i][j+1]>=a[i+1][j] && i<n && j<n)//向右
{
sum+=a[i][j+1];j++;continue;
}
if(i>=n)//只能向右
{
sum+=a[i][j++];continue;
}
if(j>=n)//只能向左
{
sum+=a[i++][j];continue;
}
}
printf("the sum is :%d\n",sum);
}
算法不好，但是可行。。。
[解决办法]
5楼 代码有问题
不用递归 不能实现的吧
4
1 2 3 4
1 1 1 1
1 1 1 1
1 9 1 1
the sum is :1
Press any key to continue
[解决办法]
[解决办法]
这个是小问题吗？我怎么见都没见过？
[解决办法]
dp可以实现。来一个差不多的例子。看懂这个可以接上面的题目
点数值三角形的最优路径搜索
【例3.8】 随机产生一个n行的点数值三角形(即三角形的每一个点都带有一个正整数),寻找从顶点开始
每一步可沿左斜（L）或右斜（R）向下至底的一条路径,使该路径所经过的点的数值和最大。例如，n=6时
给出的点数值三角形如下图所示。
7
22 11
22 9 28
5 14 23 33
11 23 1 16 6
13 8 14 32 28 3
(1） 建立递推关系
设数组b(i,j)为点(i,j)到底的最大数值和，字符数组stm(i,j)指明点(i,j)向左或向右的路标。b(i,j)与
stm(i,j)(i=n-1,…,2,1)的值由b数组的第i+1行的第j个元素与第j+1个元素值的大小比较决定，即有递推
关系：
b(i,j)=a(i,j)+b(i+1,j+1);stm(i,j)="R"
（b(i+1,j+1)>b(i+1,j)）
b(i,j)=a(i,j)+b(i+1,j);stm(i,j)="L"
（b(i+1,j+1)≤b(i+1,j)）
其中i=n-1,…,2,1
边界条件：b(n,j)=a(n,j), j=1,2,…,n。
所求的最大路径数值和即问题的最优值为b(1,1)。
(2) 逆推计算最优值
for(j=1;j<=n;j++) b[n][j]=a[n][j];
for(i=n-1;i>=1;i--) /* 逆推得b[i][j] */
for(j=1;j<=i;j++)
if(b[i+1][j+1]>b[i+1][j])
{ b[i][j]=a[i][j]+b[i+1][j+1];
stm[i][j]='R';}
else
{ b[i][j]=a[i][j]+b[i+1][j];
stm[i][j]='L';}
Printf(“%d”,b(1,1));
(3) 构造最优解
为了确定与并输出最大路径,利用stm数组从上而下查找:
先打印a(1,1),若stm(1,1)="R "，则下一个打印a(2,2),否则打印a(2,1)。
一般地,在输出i循环（i=2,3,…,n）中：
若 stm(i-1,j)="R" 则打印 "-R-";a(i,j+1);同时赋值j=j+1.
若 stm(i-1,j)="L" 则打印 "-L-";a(i,j);.
依此打印出最大路径，即所求的最优解.
[解决办法]
上面的三角图如下，上面没贴好
7
22 11
22 9 28
5 14 23 33
11 23 1 16 6
13 8 14 32 28 3
[解决办法]
怎么还没贴好，最后一次。
7
22 11
22 9 28
5 14 23 33
11 23 1 16 6
13 8 14 32 28 3
[解决办法]
呵呵，不会，只能占个沙发了，不过，期待着好的算法
[解决办法]
- C/C++ code
#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 4int a[N][N] = { 1, 2, 3, 4, 1, 2, 8, 4, 1, 10, 3, 4, 30, 2, 3, 4};int b[N*N] = {0};int bi[N*N] ={0};int bj[N*N] = {0};int main(){ int i,j,k; int left, up; for(i = 0; i < N; ++i) for(j = 0; j < N; ++j) { up = 0; left = 0; if ( i > 0 ) up = b[(i-1)*N+j]; if ( j > 0 ) left = b[i*N+j-1]; b[i*N+j] = max(up,left) + a[i][j]; printf("i: %d\t j: %d\t b: %d\n", i, j, b[i*N+j]); } printf("MAX Length: %d\n", b[N*N-1]);}
[解决办法]
算法基本上是这样吧
[解决办法]
用DP可以秒杀，何必用深搜？
[解决办法]
感谢大家，学习了；
我读了3楼的源代码并COPY下来简单的测试了
- C/C++ code
dfs(di+dir[i][0],dj+dir[i][1],count);
[解决办法]
[解决办法]
[解决办法]
回答问题给分不 算了 雷锋下
#include<stdio.h>
void main()
{
int i,j,n,a[4][4],sum;
scanf("%d",&n);//输入阶数
for(i=0;i<n;i++)//读入数组
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
i=j=0;
sum=a[i][j];//初值为第一个元素
while(i<=n-1&&j<=n-1)
{
if(a[i][j+1]>a[i+1][j])
j++;
else i++;
sum+=a[i][j];
if(j==n-1)
while(i<n-1)
{i++;
sum+=a[i][j];
}
else if(i==n-1) while(j<n-1)
{j++;
sum+=a[i][j];
}
else continue;
if(i==n-1&&j==n-1)
break;
}
printf("the sum is :%d\n",sum);
}
[解决办法]
不是在算法区回答过了么. 简单的DP,O(n2)
[解决办法]
恩，学习学习
[解决办法]
[解决办法]
新手 飘过
[解决办法]
用动态规划，写的不好，但差不多是这样子的
- C/C++ code
#include<stdio.h>int value[100][100];int max[100][100];int path[100][100];void printpath(int n,int pos){ int i = pos / n; int j = pos % n; if(path[i][j] == -1) { printf("(%d,%d)",i,j); return ; } printpath(n,path[i][j]); printf(" -> "); printf("(%d,%d)",i,j);}int main(){ int n; int i; int j; scanf("%d",&n); for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { scanf("%d",&value[i][j]); } } for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(0 == i && 0 == j) { path[i][j] = -1; max[i][j] = value[i][j]; } else if(0 == i) { path[i][j] = j-1; max[i][j] = value[i][j] + max[i][j-1]; } else if(0 == j) { path[i][j] = (i-1)*n; max[i][j] = value[i][j] + max[i-1][j]; } else { if(max[i][j-1] > max[i-1][j]) { path[i][j] = i*n + j-1; max[i][j] = value[i][j] + max[i][j-1]; } else { path[i][j] = (i-1)*n + j; max[i][j] = value[i][j] + max[i-1][j]; } } } } printf("max is %d\n",max[n-1][n-1]); printf("The path is :\n"); printpath(n,n*n-1); printf("\n");}
[解决办法]
按题意只能想左和向下走，那么从左上角到右下角就可以构成一个DAG有向无回路图
在有向无回路图上求最长路径的问题。
可以把问题转化为，把各个边的权值给成负值，求最短路径的问题。（权值定义为弧头顶点的值）
那么拓扑排序 + bellman-ford方法求最短路径问题，时间复杂度可以做到O（v +ｅ）（根据题意，题中肯定不存在负权回路，用这种方法肯定可以的）
[解决办法]
有意思。。。。。。。。。。。
[解决办法]
有意思。
[解决办法]
学习！
[解决办法]
不是吧，凡事用递归能解决的，不用递归也能解决