DP求解：数字三角形【路线问题：一般都可以用点的坐标表示】（最后一种方法是从上往下计算f[][]）
题目描述
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
算法1 go语言
(朴素版数字三角形) $O(n^2)$
package main
import (
"fmt"
"math"
)
const N = 510
var w [N][N]int
var f [N][N]int
func main() {
var n int
fmt.Scanf("%d",&n)
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
fmt.Scanf("%d", &w[i][j])
}
}
// for i, _ := range f[n] {
// f[n][i] = w[n][i] //初始化边界
// }
for j := 1; j <= n; j++ {
f[n][j] = w[n][j]
}
for i := n - 1; i >= 1; i-- {
for j := 1; j <= i; j++ {
f[i][j] = int (math.Max(float64(f[i + 1][j] + w[i][j]), float64(f[i + 1][j + 1] + w[i][j])))
}
}
fmt.Println(f[1][1])
}
算法2 C++语言
(朴素版数字三角形) $O(n^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int w[N][N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
cin >> w[i][j];
}
}
for (int j = 1; j <= n; j++)
f[n][j] = w[n][j];
for (int i = n - 1; i; i--)
{
for (int j = 1; j <= i; j++)
{
f[i][j] = max(f[i+1][j] + w[i][j], f[i+1][j+1] + w[i][j]);
}
}
cout << f[1][1];
return 0;
}
算法3 C++语言
(优化版数字三角形) $O(n^2)$
1.对于代码 f[i][j] = max( +w[][], +w[][]) 提出共同的w[i][j]
2.把w[][]和f[][]合二为一 ，将w[][] 换成 f[][]
3.f[i][j] += max( , ) ; 使用 += 运算
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
// int w[N][N]
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
cin >> f[i][j];
}
}
// for (int j = 1; j <= n; j++)
// f[n][j] = w[n][j];
for (int i = n - 1; i; i--)
{
for (int j = 1; j <= i; j++)
{
f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
}
cout << f[1][1];
return 0;
}
算法4 C++语言
(朴素版数字三角形–进行降维–二维降为一维) $O(n^2)$
降维的标准做法：
1.把 f[N][N] 第一维改成 f[2][N] —> “滚动数组”
2.把后面所有用到的 f[][] 的第一维加上 &1 即可， “&1” 相当于 模2运算
因为 & 运算符优先级低于 + 所以 f[i + 1 & 1][j] 不用加括弧
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int w[N][N], f[2][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
cin >> w[i][j];
}
}
for (int j = 1; j <= n; j++)
f[n & 1][j] = w[n][j];
for (int i = n - 1; i; i--)
{
for (int j = 1; j <= i; j++)
{
f[i & 1][j] = max(f[i+1 & 1][j] + w[i][j], f[i+1 & 1][j+1] + w[i][j]);
}
}
cout << f[1 & 1][1];
return 0;
}
go语言收获：
neepoo 的go代码
使用 fmt.Fscan() 读入数据
func Fscan(r io.Reader, a ...interface{}) (n int, err error)
import (
"fmt"
"bufio"
"os"
)
var (
n int
)
reader := bufio.NewReader(os.Stdin)
fmt.Fscan(reader, &n)
package main
import (
"fmt"
"bufio"
"os"
)
const N = 510;
var (
n int
A [N][]int
tmp int
)
func max(a, b int) int{
if a > b {
return a
}
return b
}
func main(){
reader := bufio.NewReader(os.Stdin)
fmt.Fscan(reader, &n)
for i:=1; i<=n;i++{
for j:=1;j<=i;j++{
fmt.Fscan(reader, &tmp)
A[i] = append(A[i], tmp)
}
}
for i:=n-1;i>0;i--{
for j:=0;j<i;j++{
A[i][j] += max(A[i+1][j], A[i+1][j+1])
}
}
fmt.Println(A[1][0])
}
从上往下计算的方法（数字三角形）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 510, INF = 1e9; // INF代表 ∞
int n;
int a[N][N]; // 存三角形中的每个点
int f[N][N];
int main() {
scanf("%d",&n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]); // 读入数字三角形
for (int i = 1; i <= n; i++) //为了不处理边界，先把所有边界置成 -∞
for (int j = 0; j <= i + 1; j++) //j 需要枚举到 i+1 ,就是每一行最后要多一个数，
f[i][j] = -INF; // 因为求每行末尾的f[][]时，需要右上方的值，所以需要设置多一个为 -∞
f[1][1] = a[1][1]; // 起点， 只有一个数，是确定的
for (int i = 2; i <= n; i++) //从第二行开始做，因为第一行f[1][1]已经知道了，就是a[1][1]
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i-1][j] + a[i][j]);
int res = -INF; // 所求的结果是从起点到最后一行路径上的值之和的最大值
for (int i = 1; i <= n; i++) //所以需要遍历最后一行f[n][i],然后求max()
res = max(res, f[n][i]);
printf("%d\n",res);
return 0;
}
