@@ -74,31 +74,35 @@ You totally have K weeks (each week has 7 days) to travel.
7474 */
7575public class _568 {
7676
77- /**credit: https://leetcode.com/articles/maximum-vacation-days/#approach-2-using-dfs-with-memoization-accepted*/
78- public int maxVacationDays (int [][]flights ,int [][]days ) {
79- int [][]memo =new int [flights .length ][days [0 ].length ];
80- for (int []l :memo ) {
81- Arrays .fill (l ,Integer .MIN_VALUE );
77+ public static class Solution1 {
78+ /**
79+ * credit: https://leetcode.com/articles/maximum-vacation-days/#approach-2-using-dfs-with-memoization-accepted
80+ */
81+ public int maxVacationDays (int [][]flights ,int [][]days ) {
82+ int [][]memo =new int [flights .length ][days [0 ].length ];
83+ for (int []l :memo ) {
84+ Arrays .fill (l ,Integer .MIN_VALUE );
85+ }
86+ return dfs (flights ,days ,0 ,0 ,memo );
8287 }
83- return dfs (flights ,days ,0 ,0 ,memo );
84- }
8588
86- public int dfs (int [][]flights ,int [][]days ,int curCity ,int weekno ,int [][]memo ) {
87- if (weekno ==days [0 ].length ) {
88- return 0 ;
89- }
90- if (memo [curCity ][weekno ] !=Integer .MIN_VALUE ) {
91- return memo [curCity ][weekno ];
92- }
93- int maxvac =0 ;
94- for (int i =0 ;i <flights .length ;i ++) {
95- if (flights [curCity ][i ] ==1 ||i ==curCity ) {
96- int vac =days [i ][weekno ] +dfs (flights ,days ,i ,weekno +1 ,memo );
97- maxvac =Math .max (maxvac ,vac );
89+ public int dfs (int [][]flights ,int [][]days ,int curCity ,int weekno ,int [][]memo ) {
90+ if (weekno ==days [0 ].length ) {
91+ return 0 ;
92+ }
93+ if (memo [curCity ][weekno ] !=Integer .MIN_VALUE ) {
94+ return memo [curCity ][weekno ];
95+ }
96+ int maxvac =0 ;
97+ for (int i =0 ;i <flights .length ;i ++) {
98+ if (flights [curCity ][i ] ==1 ||i ==curCity ) {
99+ int vac =days [i ][weekno ] +dfs (flights ,days ,i ,weekno +1 ,memo );
100+ maxvac =Math .max (maxvac ,vac );
101+ }
98102 }
103+ memo [curCity ][weekno ] =maxvac ;
104+ return maxvac ;
99105 }
100- memo [curCity ][weekno ] =maxvac ;
101- return maxvac ;
102106 }
103107
104108}