[LeeCode][动态规划][简单] 杨辉三角

简介: [LeeCode][动态规划][简单] 杨辉三角

递归, 还得是递归。 前面两行是固定的 (递归结束条件),从第三行开始(递归起始条件) , 求规模n (n大于3) 就是 求规模(n-1)append 当前行 (递归)。 当前行n等于前面一行 0 到 n-1 两两相加

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if(numRows == 1) {
            result.add(Arrays.asList(1));
           return result;
        }
        if(numRows == 2) {
            result.add(Arrays.asList(1));
            result.add(Arrays.asList(1,1));
            return result;
        }
        // start 3
        List<List<Integer>> beforeRows = generate(numRows - 1);
        List<Integer> curRow = getCurRow(beforeRows);
        beforeRows.add(curRow);
        return beforeRows;
    }
    public List<Integer> getCurRow(List<List<Integer>> beforeRows){
        // 取最后一行 计算当前行
        List<Integer> line = beforeRows.get(beforeRows.size() -1);
        List<Integer> curRow = new ArrayList<>();
        curRow.add(1);
        for (int i = 0;i < line.size() - 1; i++) {
            curRow.add(line.get(i) + line.get(i + 1));
        }
        curRow.add(1);
        return curRow;
    }
}
目录
相关文章
[LeeCode][动态规划][简单]上楼梯
[LeeCode][动态规划][简单]上楼梯
62 0
P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
力扣刷题记录——412. Fizz Buzz、414. 第三大的数、415. 字符串相加
力扣刷题记录——412. Fizz Buzz、414. 第三大的数、415. 字符串相加
力扣刷题记录——412. Fizz Buzz、414. 第三大的数、415. 字符串相加
|
Java 测试技术 C++
LeetCode 69. Sqrt(x)--(数组)--二分法查找 --简单
Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
138 0
LeetCode 69. Sqrt(x)--(数组)--二分法查找 --简单
【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
了解LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]。
135 0
【Day12】力扣LeetCode刷题[788.旋转数字][200.岛屿数量][509. 斐波那契数]
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)