动态规划的
1. 转移函数f[i][j]从top到第i排第j个元素的最小距离
2. 考虑到边界问题,状态转移方程为
int left = j-1<0?0:j-1;
int right = j>i-1?i-1:j;
f[i][j]=Math.min(f[i-1][left], f[i-1][right])+triangle.get(i).get(j);
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if(triangle==null || triangle.isEmpty()){ return 0; } int maxLength = triangle.get(triangle.size()-1).size(); int[][] f = new int[triangle.size()][maxLength]; f[0][0]=triangle.get(0).get(0); for(int i=1; i<triangle.size(); i++){ for(int j=0; j<i+1; j++){ int left = j-1<0?0:j-1; int right = j>i-1?i-1:j; f[i][j]=Math.min(f[i-1][left], f[i-1][right])+triangle.get(i).get(j); } } int min = f[triangle.size()-1][0]; for(int i=1; i<triangle.get(triangle.size()-1).size(); i++){ if(f[triangle.size()-1][i]<min){ min = f[triangle.size()-1][i]; } } return min; } }
相关推荐
LeetCode题解 - Java语言实现-181页.pdf
500195422331430LeetCode题解 - Java语言实现.zip
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
leetcode 答案Leetcode-Java - 符合条件(Hacktoberfest) JAVA 中的 Leetcode 答案
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
LeetCode-Python-Java zhouzhenping/LeetCode-Python&Java 参考代码来源 力扣(LeetCode) 链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 Github 01 两数之和 给定一个整数数组 ...
java lru leetcode leetcode-algorithms-java leetcode 算法笔记-java
答案leetcode-cn-java-algorithm-solution 我试图找到学习 leetcode 算法的最佳方法,所以我创建了它。 该项目将帮助您更好地学习 Leetcode 算法。 1. 入门 你想知道如何使用吗? 好的,现在让我们开始吧! 1.1 如何...
leetcode1-300.docx
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode 答案leetcode--python Leetcode 的答案
leetcode题库 leetcode-java 用Java实现leetcode题库
leetcode Leetcode-Java-解决方案 Java 中 Leetcode 问题的解决方案
leetcode 跳跃 LeetCode-Java 缺失的第一个正数 接雨水 跳跃游戏 II
leetcode 动态规划算法-1