当前位置：首页 > news >正文

力扣动态规划-16【算法学习day.110】

news 2025/7/21 13:52:53

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.三角形最小路径和

题目链接:120. 三角形最小路径和 - 力扣（LeetCode）

题面:

class Solution {List<List<Integer>> triangle;int n,m;int[][] map;int min = Integer.MAX_VALUE;int[][] f;int[][] flag;public int minimumTotal(List<List<Integer>> triangle) {this.triangle = triangle;n = triangle.size();m = triangle.get(n-1).size();map = new int[n][m];f = new int[n][m];flag = new int[n][m];for(int[] arr:flag){Arrays.fill(arr,100000);}for(int i = 0;i<n;i++){List<Integer> list = triangle.get(i);int index = 0;for(int a:list){map[i][index++] = a;}}List<Integer> list = triangle.get(n-1);for(int i = 0;i<m;i++){int blog = recursion(n-1,i);min = Math.min(min,blog);}return min;}public int recursion(int x,int y){if(flag[x][y]!=100000){return flag[x][y];}if(x==0&&y==0){return map[x][y];}int a = 0;if(x-1>=0&&y-1>=0&&(x-1)>(y-1)){a = Math.min(recursion(x-1,y),recursion(x-1,y-1));}else if(x-1>=0&&y>=0&&x-1>=y){a = recursion(x-1,y);}else if(x-1>=0&&y-1>=0){a = recursion(x-1,y-1);}else{return 100000000;}if(a==100000000||a==200000000){return 100000000;}return flag[x][y] = a+map[x][y];}
}