java语言 杨辉三角形求路径

以下是使用Java语言实现杨辉三角形求路径的代码：

import java.util.ArrayList;
import java.util.List;

public class PascalTriangle {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        if (numRows == 0) {
            return triangle;
        }

        // 第一行
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum - 1);

            // 第一个元素
            row.add(1);

            // 中间元素
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }

            // 最后一个元素
            row.add(1);

            triangle.add(row);
        }

        return triangle;
    }

    public static List<Integer> getPath(List<List<Integer>> triangle, int row, int col) {
        List<Integer> path = new ArrayList<>();

        if (triangle == null || triangle.size() == 0) {
            return path;
        }

        for (int i = 0; i < triangle.size(); i++) {
            List<Integer> currRow = triangle.get(i);

            if (i == 0) {
                path.add(currRow.get(0));
            } else {
                List<Integer> prevRow = triangle.get(i - 1);
                int left = col - 1 < 0 ? Integer.MAX_VALUE : prevRow.get(col - 1);
                int right = col >= currRow.size() ? Integer.MAX_VALUE : prevRow.get(col);

                if (left < right) {
                    col--;
                }

                path.add(currRow.get(col));
            }
        }

        return path;
    }

    public static void main(String[] args) {
        int numRows = 5;
        List<List<Integer>> triangle = generate(numRows);

        for (int i = 0; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                System.out.print(triangle.get(i).get(j) + " ");
            }

            System.out.println();
        }

        int row = 3;
        int col = 1;
        List<Integer> path = getPath(triangle, row, col);
        System.out.println("Path: " + path);
    }
}

该程序首先生成一个杨辉三角形，然后通过 `getPath()` 方法获取指定位置的路径。在 `getPath()` 方法中，我们遍历每一行并计算出路径。由于每个数字只依赖于上一行的两个数字，因此我们可以根据上一行的值来计算出当前行的值。使用这种方法，我们可以在不存储整个三角形的情况下找到路径。