AcWing 898. 数字三角形
原题链接
简单
作者:
且听水吟吟
,
2021-01-10 13:09:59
,
所有人可见
,
阅读 2
package main
import "fmt"
import "math"
func main(){
var n int
fmt.Scan(&n)
dpPre:=make([]int,n)
dp:=make([]int,n)
res:=math.MinInt32
for i:=0;i<n;i++{
for j:=0;j<=i;j++{
fmt.Scan(&dp[j])
if j==0{
dp[j]+=dpPre[0]
}else if j==i{
dp[j]+=dpPre[j-1]
}else{
dp[j]=MAX(dp[j]+dpPre[j-1],dp[j]+dpPre[j])
}
}
copy(dpPre,dp)
}
for i:=range dp{
if dp[i]>res{
res=dp[i]
}
}
fmt.Printf("%d",res)
}
func MAX(i,j int)int{
if i<j{
return j
}
return i
}