120.Triangle - 版本历史

Riguz：撤销Riguz（讨论）的版本3983

2024-01-17T15:53:59Z

撤销Riguz（讨论）的版本3983

←上一版本		2024年1月17日 (三) 15:53的版本
第38行：		第38行：
	==2D DP==		==2D DP==
	It works, but not good, especially memory.		It works, but not good, especially memory.
	{{Submission\|runtime=~~799ms~~\|memory=40.~~97MB~~\|rp=5\|mp=96.60}}		{{Submission\|runtime=3ms\|memory=44.4MB\|rp=65.79\|mp=13.95}}

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	class Solution {		class Solution {
	public int ~~numberOfBoomerangs~~(int[][] ~~points) {~~		public int minimumTotal(List<List<Integer>> triangle) {
	int ~~sum~~ = 0;		int maxRowSize = triangle.get(triangle.size() -1).size();
	for(int i = 0; i < ~~points~~.~~length;~~ i++) {		// create an array nxn to store the minimal distance that starts from triangle[i][j]
	for(int j = ~~i + 1~~; j < ~~points~~.~~length~~; j++) {		int[][] dp = new int[maxRowSize][maxRowSize];
	~~for~~( ~~int k = j + 1; k~~ < ~~points~~.length~~; k++~~) {
	~~if(~~distance~~(points,~~ i, j) =~~= distance~~(~~points,~~ i~~, k))~~		for(int i = triangle.size() -1; i >=0; i--) {
	~~sum~~ +~~= 2;~~		List<Integer> row = triangle.get(i);
	~~if(distance(points,~~ j, i) ~~== distance~~(~~points,~~ j~~, k)~~)		for(int j = 0; j < row.size(); j++) {
	~~sum += 2;~~		if(i < dp.length -1) {
	~~if(distance(points, k~~, i) =~~= distance~~(~~points, k,~~ j))		// calculate minimal distance and update
	~~sum += 2~~;		dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + row.get(j);
			} else {
			// for the bottom line, there's no subpaths
			dp[i][j] = row.get(j);
	}		}
	}		}
	}		}
	return ~~sum;~~		return dp[0][0];
	}

	~~private static int distance(int[][] points, int i, int j) {~~
	~~int l = points[i]~~[0~~] - points[j~~][0];
	~~int w = points[i][1] - points[j][1];~~
	~~return l * l + w * w~~;
	}		}
	}		}

Riguz：/* 2D DP */

2024-01-17T15:52:37Z

2D DP

←上一版本		2024年1月17日 (三) 15:52的版本
第38行：		第38行：
	==2D DP==		==2D DP==
	It works, but not good, especially memory.		It works, but not good, especially memory.
	{{Submission\|runtime=~~3ms~~\|memory=44.~~4MB~~\|rp=~~65.79~~\|mp=13.95}}		{{Submission\|runtime=799ms\|memory=40.97MB\|rp=5\|mp=96.60}}

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	class Solution {		class Solution {
	public int ~~minimumTotal~~(~~List<List<Integer>> triangle) {~~		public int numberOfBoomerangs(int[][] points) {
	int ~~maxRowSize = triangle.get(triangle.size() -1).size();~~		int sum = 0;
	~~// create an array nxn to store the minimal distance that starts from triangle~~[i][j]		for(int i = 0; i < points.length; i++) {
	int~~[][] dp~~ = ~~new int[maxRowSize][maxRowSize]~~;		for(int j = i + 1; j < points.length; j++) {
			for( int k = j + 1; k < points.length; k++) {
	for(int i ~~= triangle.size() -1; i >~~=0; i~~--) {~~		if(distance(points, i, j) == distance(points, i, k))
	~~List~~<~~Integer> row = triangle~~.~~get(~~i);		sum += 2;
	for(int j = 0; j < ~~row~~.~~size()~~; j++) {		if(distance(points, j, i) == distance(points, j, k))
	if(i < dp.length -1) {		sum += 2;
	~~// calculate minimal~~ distance ~~and update~~		if(distance(points, k, i) == distance(points, k, j))
	~~dp[~~i][j] = ~~Math.min~~(~~dp[~~i+~~1][~~j], ~~dp[~~i~~+1][j+1]~~) ~~+ row.get~~(j);		sum += 2;
	~~} else {~~
	~~// for the bottom line~~, ~~there's no subpaths~~
	~~dp[~~i~~][j]~~ = ~~row.get~~(j);
	}		}
	}		}
	}		}
	return dp[0][0];		return sum;
			}

			private static int distance(int[][] points, int i, int j) {
			int l = points[i][0] - points[j][0];
			int w = points[i][1] - points[j][1];
			return l * l + w * w;
	}		}
	}		}

Riguz：Riguz moved page LeetCode:120.Triangle to 120.Triangle without leaving a redirect

2023-09-23T13:07:51Z

Riguz moved page LeetCode:120.Triangle to 120.Triangle without leaving a redirect

←上一版本		2023年9月23日 (六) 13:07的版本
（没有差异）

Riguz：/* 1D DP */

2023-09-23T06:14:19Z

1D DP

@@ 第87行： / 第87行： @@
+         }
          return dp[0];
+     }
+}

Riguz：/* Memory Optimization */

2023-09-23T06:04:28Z

Memory Optimization

←上一版本		2023年9月23日 (六) 06:04的版本
第64行：		第64行：
	</syntaxhighlight>		</syntaxhighlight>

	== ~~Memory Optimization~~==		== 1D DP==
	{{Submission\|runtime=2ms\|memory=43.61MB\|rp=77.3\|mp=89.2}}		{{Submission\|runtime=2ms\|memory=43.61MB\|rp=77.3\|mp=89.2}}

Riguz：/* First attampt */

2023-09-23T06:04:14Z

First attampt

←上一版本		2023年9月23日 (六) 06:04的版本
第36行：		第36行：

	=Solution=		=Solution=
	==~~First attampt~~==		==2D DP==
	It works, but not good, especially memory.		It works, but not good, especially memory.
	{{Submission\|runtime=3ms\|memory=44.4MB\|rp=65.79\|mp=13.95}}		{{Submission\|runtime=3ms\|memory=44.4MB\|rp=65.79\|mp=13.95}}

Riguz：/* Memory Optimization */

2023-09-23T06:03:44Z

Memory Optimization

←上一版本		2023年9月23日 (六) 06:03的版本
第70行：		第70行：
	class Solution {		class Solution {
	public int minimumTotal(List<List<Integer>> triangle) {		public int minimumTotal(List<List<Integer>> triangle) {
			// 可以直接用 triangle.size();
	int maxRowSize = triangle.get(triangle.size() -1).size();		int maxRowSize = triangle.get(triangle.size() -1).size();
	// 只需要记录上一次的最短路径		// 只需要记录上一次的最短路径

Riguz：/* Solution */

2023-09-23T05:56:57Z

Solution

←上一版本		2023年9月23日 (六) 05:56的版本
第65行：		第65行：

	== Memory Optimization==		== Memory Optimization==
			{{Submission\|runtime=2ms\|memory=43.61MB\|rp=77.3\|mp=89.2}}

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">

Riguz：/* First attampt */

2023-09-23T05:54:13Z

First attampt

←上一版本		2023年9月23日 (六) 05:54的版本
第38行：		第38行：
	==First attampt==		==First attampt==
	It works, but not good, especially memory.		It works, but not good, especially memory.
			{{Submission\|runtime=3ms\|memory=44.4MB\|rp=65.79\|mp=13.95}}
	* Runtime 3 ms
	* Beats 65.79%
	* Memory 44.4 MB
	* Beats 13.95%

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">

Riguz：/* Description */

2023-09-23T05:28:28Z

Description

←上一版本		2023年9月23日 (六) 05:28的版本
第1行：		第1行：
	=Description=		=Description=
	{{LeetCode\|id=triangle\|no=120\|title=Triangle}}		{{LeetCode
			\|id=triangle
	Given a triangle array, return the minimum path sum from top to bottom.		\|no=120
			\|difficulty=Medium
			\|category=Dynamic Programming
			\|collection=Top 150
			\|title=Triangle
			\|summary=Given a triangle array, return the minimum path sum from top to bottom.}}

	For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.		For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

120.Triangle - 版本历史

Riguz：​撤销Riguz（讨论）的版本3983

Riguz：​/* 2D DP */

Riguz：​Riguz moved page LeetCode:120.Triangle to 120.Triangle without leaving a redirect

Riguz：​/* 1D DP */

Riguz：​/* Memory Optimization */

Riguz：​/* First attampt */

Riguz：​/* Memory Optimization */

Riguz：​/* Solution */

Riguz：​/* First attampt */

Riguz：​/* Description */

Riguz：撤销Riguz（讨论）的版本3983

Riguz：/* 2D DP */

Riguz：Riguz moved page LeetCode:120.Triangle to 120.Triangle without leaving a redirect

Riguz：/* 1D DP */

Riguz：/* Memory Optimization */

Riguz：/* First attampt */

Riguz：/* Memory Optimization */

Riguz：/* Solution */

Riguz：/* First attampt */

Riguz：/* Description */