数字三角形(dfs+动态规划）通过率未达100%

数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N (1≤N≤100)N (1≤N≤100)，表示三角形的行数。

下面的 NN 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

一、若无红色加粗文字：

代码：

##数字三角形
#斜着走
##动态规划
##状态:dp[i][j]表示从i,j出发可以达到的最大值
##状态转移:左下方或者右下方加起来取值最大 当前状态可以由之前的什么子问题得来,肯定是希望
##从当前位置走到下方值大的一个数字,那么和还要加上当前的,由于需要后面的因此倒起来
##最后一行为边界条件,等于自己,从最后一行开始往下走最大值就是自己
##max(dp[i+1][j],dp[i+1][j+1])+a[i][j]
n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(i+1):
##        注意这里是i+1 每行i个数字 上面是n-1 相当于-2故这里是i+1
        if i==n-1:
            dp[i][j]=a[n-1][j]
        else:
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]

print(dp[0][0])

二、有红色加粗文字 ：

代码：

这里的意思相当于不管前面是怎么走的,前面求出的就是相应位置会得到的最大值,在最后结果那里判断,根据左右步数不超过1,而不超过1的情况有3种,例如左右左偏左,右左右偏右，以及左右左右这种，因此可以发现如果是走奇数步那么一定会偏,走偶数步那么一定会回到正中间。因此后面直接判断即可，同时这里其实没有要求那么严没有在走的过程中保持不超过1 

动态规划

##数字三角形
##动态规划
##dp[i][j]表示达到i行j列的时候可以取得的最大值
##状态转移 从左上右上而来,还是两者都可以取最大值
n=int(input())
a=[]
dp=[[0]*(n) for _ in range(n)]
for i in range(n):
##从0开始    
    a.append(list(map(int,input().split())))
dp[0][0]=a[0][0]
for i in range(1,n):
    for j in range(i+1):
##       从上方而来
        if j==0:
            dp[i][j]=dp[i-1][j]+a[i][j]
##       从左上方来
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+a[i][j-1]
##     可以来自左上方也可以来自右下方
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
##如果是奇数其实走的是偶数步 要达到不超过1 那么回到中线
##dp[n][j//2]
##如果是偶数,其实走的是奇数步 那么即可能偏左也可能偏右
##    就取最大值两边的  
if n%2==0:
    print(max(dp[n-1][n//2-1],dp[n-1][n//2]))
else:
    print(dp[n-1][n//2])

深度优先搜索: 

代码：

import sys
import os
sys.setrecursionlimit(10000000)
n=int(input())
a=[]
ans=0
for i in range(n):
    a.append(list(map(int,input().split())))
##深度优先搜索
def dfs(depth,col,tot,left,right):
##    当前所处的行 列 和 左下方次数 右下方次数
##    depth表示第i行
      if depth==n-1:
        global ans
        if abs(left-right)<=1:
            ans=max(ans,tot)
        return
      if col<len(a[depth+1]):
        dfs(depth+1,col,tot+a[depth+1][col],left+1,right)
      if col+1<len(a[depth+1]):
        dfs(depth+1,col+1,tot+a[depth+1][col+1],left,right+1)
dfs(0,0,a[0][0],0,0)
print(ans)