[leetcode] #55 Jump Game & #120 Triangle

Title - #55 Jump Game

Level - Medium

Description - 題目主要是給一個字串 S = [1,2,3]，每個數字代表可行的距離，求能否到達最後一個字原。

(補充)

Greedy 很明顯，也沒有什麼難度... 大概就是給個超級長的字串，但是若得到足夠的數字就可以直接結束程式，屬於O(n)。

作法 iteration

(略)

Title - #120 Triangle

Level - Medium

Description - 題目主要是給一個nested List = [[1],[2,3],[4,5,6]]，呈現triangle狀，每個數字代表cost。題目要求traverse從第一個List走到最後一個List，只能走adjacent elements，相是

  1

 2 3

4 5 6

只能走1-2-5 而非 1-2-6。

(補充)

DP問題，主要是記住上次的COST，而且每次的選擇C(i)僅會參照先前min(prevC(i), prevC(i-1))加上C(i)得到total cost at i-th node。不過題目希望僅用一個O(N)的空間複雜度完成，所以多了兩個變數使用，加上須小心處理每個List的1st & last node即可。

作法 iteration

1:  for (int i=0;i<S.size();i++) {  
2:   row <- S[i];  
3:   for (int j=0;j<row.size();j++) {  
4:    if (j=0) c0=0;  
5:    else   c0=c1;  
6:    if (j<i)  c1 = last[j];  
7:    if (j=0) min = c1;  
8:    else   min = minimum(c0,c1);  
9:    last[j] = min + row[j];  
10:   }  
11:  }  

Java 問題：
1. 在 java 除local variable似乎不需要初始化，所有物件的宣告的元素初始值為0。 From stackoverflow