题目描述
数字三角形(DP)
算法1
(DP)
思路
Step1 状态表示,eg:路线f(i,j);需要通过经验获得,题海战术;属性,包括max,min,num
Step2 状态计算(集合划分),推导得来,注意此题的集合定义,eg:从底往上走到(i,j)的所有路线的集合。
时间复杂度
$O(n^2)$
参考文献
【由数据范围反推算法复杂度以及算法内容】https://www.acwing.com/blog/content/32/
JAVA1 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int N = 510;
static int[][] f = new int[N][N];
public static void main(String[] args){
int n = in.nextInt();
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j] = in.nextInt();
}
}
for(int i=n-1;i>0;i--){
for(int j=1;j<=i;j++){
f[i][j] += Math.max(f[i+1][j],f[i+1][j+1]);
}
}
System.out.println(f[1][1]);
}
}
JAVA2 代码(降维后)
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int N = 510;
static int[][] w = new int[N][N];
static int[][] f = new int[**2**][N];
public static void main(String[] args){
int n = in.nextInt();
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
w[i][j] = in.nextInt(); //or
//f[i & 1][j] = in.nextInt();//也可
}
}
for(int i=n-1;i>0;i--){
for(int j=1;j<=i;j++){
f[i & 1][j] += Math.max(f[i+1 & 1][j],f[i+1 & 1][j+1]);
}
}
System.out.println(f[1][1]);
}
}