三角形最小路径和-白红宇

三角形最小路径和

阅读量：3959 次

发布时间：2019-05-24

本文共 663 字，大约阅读时间需要 2 分钟。

题目来源

题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

解法一：动态规划

在这里插入图片描述

class Solution {
       public int minimumTotal(List
   
    
     > triangle) {
           int n=triangle.size();//求三角形的长度        int[][] f=new int[n][n];//创建二维数组用[i][j]表示位置        f[0][0]=triangle.get(0).get(0);        for(int i=1;i

在这里插入图片描述

解法二：动态规划+空间优化

在这里插入图片描述

class Solution {
       public int minimumTotal(List
   
    
     > triangle) {
           int n=triangle.size();        int[][] f=new int[2][n];        f[0][0]=triangle.get(0).get(0);        for(int i=1;i

上述方法的时间复杂度为O（n）使用了2n的空间存储状态

转载地址：http://xnlzi.baihongyu.com/

你可能感兴趣的文章