我要招人

去企业版

首页 > 试题广场 >

三角形取数(Hard Version)

[编程题]三角形取数(Hard Version)

热度指数：1367 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个由 $n$ 行构成的数字三角形。第 $i$ 行共有 $2i-1$ 个整数，整体形状如下图所示（以 $n=3$ 为例）：

$\hspace{15pt}$ 从顶点（第一行唯一的数字）出发，依次向下移动恰好 $n-1$ 次直到抵达最后一行。
$\hspace{15pt}$ 假设当前位于第 $i$ 行第 $j$ 列：
${\hspace{20pt}}_\texttt{1.}\,$ 可以向正下方移动至第 $(i+1)$ 行第 $j$ 列；
${\hspace{20pt}}_\texttt{2.}\,$ 可以向左下方移动至第 $(i+1)$ 行第 $(j-1)$ 列；
${\hspace{20pt}}_\texttt{3.}\,$ 可以向右下方移动至第 $(i+1)$ 行第 $(j+1)$ 列。

$\hspace{15pt}$ 每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为 $l$ ，向右下方移动的次数记为 $r$ 。我们需要满足

$\left|l-r\right|\leqq k$

$\hspace{15pt}$ 请你选择一条合法路径，使得获得数值之和最大，并输出该最大值。

输入描述:

在一行上输入两个整数 ，分别表示数字三角形的行数与允许的移动差。 
此后  行，第  行输入  个整数 



共计  个整数。

输出描述:

输出一个整数，表示满足条件的路径可以取得的最大数值之和。

示例1

输入

输出

说明

在该样例中，可选取的最大路径为 
第  行：取 ； 
第  行：向右下方移动，取 ； 
第  行：向正下方移动，取 。 
总和为 ，且 。

示例2

输入

输出

算法知识视频讲解

查看答案及解析

Java

BraveCoder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final long INF = -1_000_000_000_000_000_000L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 初始化数字三角形数组
        long[][] nums = new long[n][];
        for (int i = 0; i < n; i++) {
            nums[i] = new long[2 * i + 1];
            for (int j = 0; j < 2 * i + 1; j++) {
                nums[i][j] = sc.nextLong();
            }
        }

        // 初始化dp数组
        long[][] dp = new long[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new long[2 * i + 1];
        }

        // 数字三角形数组最后一行（n-1）行赋值
        int center = n - 1;
        for (int j = 0; j < 2 * n - 1; j++) {
            if (Math.abs(j - center) <= k) {
                dp[n - 1][j] = nums[n - 1][j];
            } else {
                dp[n - 1][j] = INF;
            }
        }

        // 从下向上递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= 2 * i; j++) {
                long maxNext = Math.max(dp[i + 1][j], Math.max(dp[i + 1][j + 1], dp[i + 1][j + 2]));
                if (maxNext > INF) {
                    dp[i][j] = nums[i][j] + maxNext;
                } else {
                    dp[i][j] = INF;
                }
            }
        }

        System.out.println(dp[0][0]);
    }
}

发表于 2025-09-26 11:54:52 回复(0)

C++

icepointboy

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> vec;
    vector<vector<long long>>dp;
    for(int i=0;i<n;i++){
    vec.push_back(vector<int>(2*i+1,0));
    dp.push_back(vector<long long>(2*i+1,LLONG_MIN));
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<2*i+1;j++)
    cin>>vec[i][j];
    dp[0][0]=vec[0][0];
    for(int i=1;i<n;i++)
        for(int j=0;j<2*i+1;j++)
            for(int l=max(0,j-2);l<=min(j,2*i-2);l++)
                dp[i][j]=max(dp[i][j],vec[i][j]+dp[i-1][l]);
    int index=n-1;
    for(int i=0;i<2*n-1;i++)
    if(dp[n-1][i]>dp[n-1][index]&&abs(n-1-i)<=k)
    index=i;
    cout<<dp[n-1][index];
}

发表于 2025-10-27 15:54:17 回复(0)

牛客156913013号

超简单dfs:

from math import inf
import sys
from functools import cache

n, k = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))


def get_mid(i):
    # 第i行的中间坐标
    return i

@cache
def dfs(x, y):
    """x: 行, y: 当前列的偏移量"""
    if x == n-1:
        return arr[x][y+get_mid(x)] if abs(y) <= k else -inf
    return arr[x][y+get_mid(x)] + max(dfs(x+1, y-1), dfs(x+1, y), dfs(x+1, y+1))

print(dfs(0, 0))

发表于 2025-09-24 14:26:24 回复(0)

提交观点

问题信息

来自：华为机试编程模拟题4

难度：

3条回答 30收藏 514浏览

三角形取数(Hard Version)

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题