首页 > 试题广场 >

数字三角形

[编程题]数字三角形
  • 热度指数:2138 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5
如上图所示,从一个数字三角形的顶部走到底部有很多条不同的路径,规则是只能从当前节点走到下一层相邻的节点,即下一层的左边或右边。例如第三行第二个数字“1”只能走到第四行的第二个数字“7”与第三个数字“4”。
请寻找最佳一条路径,使得这条路径上节点的数字总和最大。

输入描述:
输入包含多组。每组数据的第一行包含一个正整数n(1≤n≤100),代表三角形的层数。

紧接着有n行数字,第i(1≤i≤n)行包含i个自然数。


输出描述:
对应每组数据,输出最大的和。
示例1

输入

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

输出

30

#include<iostream>
#include<vector>
usingnamespacestd;
intmain()
{
   intn;
   while(cin>>n)
   {
     vector<vector<int>> input(n,vector<int>(n));
       for(inti=0;i<n;i++)
       {
           for(intj=0;j<=i;j++)
                cin>>input[i][j];
       }
       for(inti=n-2;i>=0;i--)
       {
           for(intj=0;j<=i;j++)
           {
               input[i][j]+=max(input[i+1][j],input[i+1][j+1]);
           }
       }
       cout<<input[0][0]<<endl;
   }
   return0;
}
编辑于 2017-10-31 16:45:06 回复(0)

逐层逐层流下来,加上上层的值,保留最大值。
左右边界必定加上对应上层的左右边界,可以先从把边界变化了
然后比较加上上一个或左上那个,保存最大。
输出最后一层的最大值即为答案

发表于 2018-09-24 00:46:18 回复(0)

python solution:

while True:
    try:
        ***, length = [], int(input())
        for i in range(length):
            ***.append(list(map(int, input().split())))
        for i in range(1, length):
            ***[i][0] += ***[i - 1][0]
            ***[i][-1] += ***[i - 1][-1]
        for i in range(2, length):
            for j in range(1, i):
                ***[i][j] += max(***[i - 1][j - 1], ***[i - 1][j])
        print (max(***[-1]))
    except:
        break
发表于 2017-11-15 22:00:14 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
    	vector<vector<int>> input(n,vector<int>(n));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
				cin>>input[i][j];
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=0;j<=i;j++)
            {
                input[i][j]+=max(input[i+1][j],input[i+1][j+1]);
            }
        }
        cout<<input[0][0]<<endl;
    }
    return 0;
}

发表于 2017-09-09 22:44:07 回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int n;
	while (cin >> n && n > 0)
	{
		vector<vector<int>> dp(n + 1, vector<int>(n + 1,0));
		int num;
		for (int i = 1; i <= n; ++i)
		{
			cin >> num;
			dp[i][1] = dp[i - 1][1] + num;
			for (int j = 2; j <= i; ++j)
			{
				cin >> num;
				if (j == i) dp[i][j] = dp[i - 1][j - 1] + num;
				else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num;
			}
		}

		int maxPath = 0;
		for (auto& i : dp[n]) maxPath = max(maxPath, i);
		cout << maxPath << endl;
	}

	return 0;
}

发表于 2017-07-11 18:57:27 回复(0)
动态规划的典型题目

从上往下,使用f数组存储中间结果,进行迭代更新,是f数组处于最优状态

重点:计算当前行时,使用max更新f的下一行,是下一行存储最大结果

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	while (cin >> n)
	{
        // 数据输入
		vector<vector<int> > d(n, vector<int>(n));
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= i; j++)
				cin >> d[i][j];
        // 初始化f数组
		vector<vector<int> > f(n, vector<int>(n));
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				f[i][j]=0;
		f[0][0] = d[0][0];
        
        // 从上往下迭代计算 - 标准动态规划
		for (int i = 0; i < n-1; i++)
			for (int j = 0; j <= i; j++)
			{
				f[i + 1][j] = max(f[i + 1][j], f[i][j] + d[i + 1][j]);
				f[i + 1][j + 1] = max(f[i+1][j+1],f[i][j]+d[i+1][j+1]);
			}
        // 找出最大结果,输出
		sort(f[n - 1].begin(), f[n - 1].end());
		cout << f[n - 1][n-1] << endl;
	}
	return 0;
}

发表于 2016-09-01 16:13:30 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        vector<vector<int> > arr(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<i+1;j++){
                int num=0;
                cin>>num;
                arr[i].push_back(num);
            }    
        }
        vector<vector<int> > dp(n,vector<int>(n,0));
        dp[0][0]=arr[0][0];
        for(int i=1;i<n;i++)
            dp[i][0]=dp[i-1][0]+arr[i][0];
        for(int i=1;i<n;i++)
            dp[i][arr[i].size()-1]=arr[i][arr[i].size()-1]+dp[i-1][arr[i-1].size()-1];   
        for(int i=2;i<n;i++){
            for(int j=1;j<i;j++){
                int temp=dp[i-1][j-1]>dp[i-1][j]? dp[i-1][j-1]:dp[i-1][j];
                dp[i][j]=arr[i][j]+temp;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(ans<dp[n-1][i])
                ans=dp[n-1][i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2016-08-29 17:09:35 回复(0)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		vector<vector<int> > m;
		for (int i = 0; i < n; ++i)
		{
			vector<int> cell(i + 1, 0);
			for (int j = 0; j <= i; ++j)
				cin >> cell[j];
			m.push_back(cell);
		}

		for (int i = n - 2; i >= 0; --i)
			for (int j = 0; j <= i; ++j)
				m[i][j] += max(m[i + 1][j], m[i + 1][j + 1]);

		cout << m[0][0] << endl;
	}

	return 0;
}

发表于 2015-12-16 15:50:16 回复(0)
public class Main{
    public static void main(String[] args)  {
    Scanner sc=new Scanner(System.in);
    while(sc.hasNext()) {
        int n =sc.nextInt();
        int[][] bp=new int[n+1][n+1];
         for(int i=1;i<n+1;i++)
         {
            for(int j=1;j<i+1;j++)
            {
                bp[i][j]=sc.nextInt();
            }
         }
        
         int max=Integer.MIN_VALUE;
         for(int i=1;i<n+1;i++)
         {
            for(int j=1;j<n+1;j++)
            {            
            bp[i][j]+=Math.max(bp[i-1][j], bp[i-1][j-1]);            
            max=Math.max(max, bp[i][j]);
            } 
         }
        System.out.println(max);
         
    }

}
发表于 2020-08-27 10:46:22 回复(0)
注意两点:
1.while循环输入,处理多个case
2.使用数组存已经计算好的代价,去掉重复计算,降低时间复杂度
import java.util.Scanner;

public class Main {
    public static  int MaxSum(int x,int y,int N,int[][] array,int[][] maxSum )
    {
        if(maxSum[x][y]!=-1)
        {
            return maxSum[x][y];
        }
        if(x==N-1)
        {

            return maxSum[x][y]=array[x][y];
            
        }
        else
        {
            int xx=MaxSum(x+1,y,N,array,maxSum);
            int yy=MaxSum(x+1,y+1,N,array,maxSum);
            maxSum[x][y]=Math.max(xx,yy)+array[x][y];
            return maxSum[x][y];
        }
    }

    public static void main(String[] args) {
        int N;
        Scanner reader =new Scanner(System.in);
        while(reader.hasNextInt())
        {
            N = reader.nextInt();
            int[][] array=new int [N][N]; 
            int[][] maxSum=new int[N][N];
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    maxSum[i][j]=-1;
                }
            }
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    array[i][j]=reader.nextInt();
                }
            }
            System.out.println(MaxSum(0,0,N,array,maxSum));
        }
    }
}

发表于 2019-09-04 20:49:33 回复(0)

从下往上计算,每次res[i][j]由i+1层的数据中最大值往下计算,取其中最大值

while True:
    try:
        n = int(input())
        res = [list(map(int,input().split())) for i in range(n)]
        for i in range(n-2,-1,-1):
            for j in range(i+1):
                res[i][j] = res[i][j] + max(res[i+1][j],res[i+1][j+1])
        print(res[0][0])
    except:break
发表于 2019-07-16 08:59:16 回复(0)
//如果直接递归,时间复杂度是2^n,记忆+递归,时间复杂度降为n^2

#include<stdio.h>
#define Max 100


int a[Max + 1][Max + 1];
int d[Max + 1][Max + 1];

int N;//总层数


int fun(int x, int y) {//x行数,y列数,a[x][y]
    if (x > N) return 0;//y越界时x一定越界,所以不用限制y
    if (d[x][y]) return d[x][y];//如果之前已经计算过,则直接返回结果


    //如果之前没计算过,计算并记忆
    d[x + 1][y + 1] = fun(x + 1, y + 1);
    d[x + 1][y] = fun(x + 1, y);
    d[x][y] = a[x][y] + ((d[x + 1][y + 1] > d[x + 1][y]) ? d[x + 1][y + 1] : d[x + 1][y]);
    return  d[x][y];
}


int main() {
    int i,j;

    while (scanf("%d", &N) != EOF) {
        for (i = 1; i <= N; i++)
            for (j = 1; j <= i; j++)
                d[i][j] = 0;
        for (i = 1; i <= N; i++)
            for (j = 1; j <= i; j++)
                scanf("%d", &a[i][j]);

        printf("%d\n", fun(1, 1));
    }

    return 0;
}
发表于 2019-05-11 09:11:20 回复(0)

/数塔问题/

#include<stdio.h>
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n;
int i,j;
while(scanf("%d",&n)!=EOF){
int matrix[n][n];
int dp[n][n];
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
scanf("%d",&matrix[i][j]);
dp[i][j]=matrix[i][j];
}
}
//前面是输入操作
//下面是从下往上选最大的,dp[i][j]表示到matrix[i][j]所累积的最大值
for(i=n-2;i>=0;i--){
for(j=i;j>=0;j--){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+matrix[i][j];
}
}
printf("%d\n",dp[0][0]);
}
}

发表于 2019-03-26 10:28:18 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int a[100][100] = {0};
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= i; ++j)
                cin >> a[i][j];
        int maxPath = a[0][0];
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
                maxPath = max(maxPath, a[i][j]);
            }
        }
        cout << maxPath << endl;
    }
    return 0;
}


发表于 2018-02-22 14:31:07 回复(0)
import java.util.Scanner;

public class TrangleDemo {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int[][] nums=new int[n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<=i;j++) {
                    nums[i][j]=sc.nextInt();
                }
            }
            int[][] dp=new int[n][n];
            for(int i=n-1;i>=0;i--) {
                for(int j=0;j<=i;j++) {
                    if(i==n-1) {
                        dp[i][j]=nums[i][j];
                    }else {
                        dp[i][j]=Math.max(dp[i+1][j]+nums[i][j], dp[i+1][j+1]+nums[i][j]);
                    }
                    
                }
            }
            System.out.println(dp[0][0]);
        }
    }
}

发表于 2018-01-26 14:54:45 回复(0)
import java.util.Scanner;

/**
 * Created by Olive on 2017/9/7.
 * <p>
 * 7
 * 3 8
 * 8 1 0
 * 2 7 4 4
 * 4 5 2 6 5
 * 如上图所示,从一个数字三角形的顶部走到底部有很多条不同的路径,
 * 规则是只能从当前节点走到下一层相邻的节点,即下一层的左边或右边。
 * 例如第三行第二个数字“1”只能走到第四行的第二个数字“7”与第三个数字“4”。
 * 请寻找最佳一条路径,使得这条路径上节点的数字总和最大。
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[][] array = new int[n + 1][n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= i; j++)
                    array[i][j] = in.nextInt();
            }
            System.out.println(findMax(array, n));
        }
    }

    public static int findMax(int[][] array, int n) {
        if (array == null || array.length == 0 || array[0].length == 0 || n == 0)
            return 100;

        // dp[i][j]表示选择了第i层的第j个数字作为结尾的最大和
        int[][] dp = new int[n + 1][n + 1];
        int max = 0;

        // 第一行只能由上一层第一行访问
        for (int i = 1; i <= n; i++) {
            dp[i][1] = dp[i - 1][1] + array[i][1];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1] , dp[i - 1][j]) + array[i][j];
                if (dp[i][j] > max)
                    max = dp[i][j];
            }
        }
        return max;
    }
}


发表于 2017-09-07 16:34:52 回复(0)
第一种方法:直接使用递归(超时,递归导致重复计算太多,且时间复杂度为2的n次方)
#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;
int D[MAX][MAX] = {0};
int n = 0;

int MaxSum(int i, int j)
{
if(i == n)
return D[i][j];
int x =  MaxSum(i + 1, j);
int y = MaxSum(i + 1, j + 1);
return max(x, y) + D[i][j];
}


int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
scanf("%d", &D[i][j]);
}
}
printf("%d\n", MaxSum(1, 1));
return 0;
}

第二种方法:递归+动态规划
#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;
int D[MAX][MAX] = {0};
int maxSum[MAX][MAX] = {0};
int n = 0;

int MaxSum(int i, int j)
{
    if(maxSum[i][j] != -1)
        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()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                cin >> D[i][j];
                maxSum[i][j] = -1;
            }
        }
        cout << MaxSum(1, 1) << endl;
    }
    return 0;
}
第三种:优化(递归需要使用大量的堆栈上的空间,很容易栈溢出)
#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;
int D[MAX][MAX] = {0};
int maxSum[MAX][MAX] = {0};
int n = 0;

int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                cin >> D[i][j];
            }
        }
        for(int j = 1; j <= n; j++)
        {
            maxSum[n][j] = D[n][j];
        }
        for(int i = n - 1; i >= 1; i--)
        {
            for(int j = 1; j <= i; j++)
            {
                maxSum[i][j] = max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
            }
        }
        cout << maxSum[1][1] << endl;
    }
    return 0;
}

第四种方法:空间优化
#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;
int D[MAX][MAX] = {0};
int* maxSum = nullptr;
int n = 0;

int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                cin >> D[i][j];
            }
        }
        maxSum = D[n]; // 指针指向最后一行
        for(int i = n - 1; i >= 1; i--)
        {
            for(int j = 1; j <= i; j++)
            {
                maxSum[j] = max(maxSum[j], maxSum[j+1]) + D[i][j];
            }
        }
        cout << maxSum[1] << endl;
    }
    return 0;
}
编辑于 2017-08-28 11:27:41 回复(1)
// write your code here cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    while( cin>>n&&n>0){
      int *maxSum;
      int num[101][101];
      for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>num[i][j];
    maxSum=num[n];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
            maxSum[j]=max(maxSum[j],maxSum[j+1])+num[i][j];
    cout<<maxSum[1]<<endl;
        
  }
}

发表于 2017-08-22 17:48:36 回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int d[100][100];
int result[100][100];

int dp(int i,int j,int n){
    if(i==n-1) {
		result[i][j]=d[i][j];
		return result[i][j];
	}
	if(result[i][j]!=-1)
		return result[i][j];
    else{
		int x=dp(i+1,j,n);
		int y=dp(i+1,j+1,n);
		result[i][j]=max(x,y)+d[i][j];
        return result[i][j];
    }
}

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
				cin>>d[i][j];
				result[i][j]=-1;
			}
        }
        cout<<dp(0,0,n)<<endl;
    }
    return 0;
}

发表于 2017-07-19 20:11:42 回复(0)

可以参考文章数字三角形–动态规划

编辑于 2017-06-06 10:07:17 回复(0)