[Leetcod] 120. Triangle

12038 ワード
algorithm テキストリンク
https://leetcode.com/problems/triangle/
入力:リスト形式の変数(三角形タワーとして表すことができる)
出力:三角形の塔の最上部から、隣接する数字を加えると、最小と

(上図のように)
BFSまたはDFSを使用して解凍するとタイムアウトします.
DP方式でアクセスする必要があります.
三角形タワーのような変数を作成し、各インデックスに始点からインデックスまでの最小和を格納します.最後の行に下がると、最後の行で最小値が検索されます.
コード#コード#
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
		List<List<Integer>> dp = new ArrayList<List<Integer>>();
		dp.add(triangle.get(0));

		for (int i = 1; i < triangle.size(); i++) {
			List<Integer> l = new ArrayList<Integer>();
			for (int j = 0; j < triangle.get(i).size(); j++) {
				if (j == 0) {
					l.add(dp.get(i - 1).get(j) + triangle.get(i).get(j));
				} else if (j == triangle.get(i).size() - 1) {
					l.add(dp.get(i - 1).get(j - 1) + triangle.get(i).get(j));
				} else {
					l.add(dp.get(i - 1).get(j) < dp.get(i - 1).get(j - 1)
							? dp.get(i - 1).get(j) + triangle.get(i).get(j)
							: dp.get(i - 1).get(j - 1) + triangle.get(i).get(j));
				}
			}
			dp.add(l);
		}

		int min = Integer.MAX_VALUE;
		for (Integer i : dp.get(dp.size() - 1)) {
			if (i < min)
				min = i;
		}
		return min;
    }
memset、memmcpy、memmove実装とその違い
[Replit] Sementic Web, Semantic Tags