package Ġle et code _ study _ badge . dynamic _ programming Ċ Ċ class ĠDay 3 Ġ{ ĊĠĠĠ Ġ// Ġhttps :// leetcode . com / problems / house - rob ber / ĊĠĠĠ Ġfun Ġrob ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdp Ġ= Ġnums . clone () ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġnums . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġi Ġ+ Ġ 2 Ġuntil Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ j ] Ġ= Ġmax Of ( dp [ j ], Ġnums [ j ] Ġ+ Ġdp [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġmax I Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġdp . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax I Ġ= Ġmax Of ( it , Ġmax I ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġmax I ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġoptim izing ĊĠĠĠ Ġfun Ġhouse Rob ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . size Ġ== Ġ 1 ) Ġreturn Ġnums [ 0 ] ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . size Ġ== Ġ 2 ) Ġreturn Ġmax Of ( nums [ 0 ], Ġnums [ 1 ]) ĊĠĠĠĠĠĠĠ Ġval Ġdp Ġ= ĠInt Array ( nums . size ) ĊĠĠĠĠĠĠĠ Ġdp [ 0 ] Ġ= Ġnums [ 0 ] ĊĠĠĠĠĠĠĠ Ġdp [ 1 ] Ġ= Ġmax Of ( nums [ 0 ], Ġnums [ 1 ]) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 2 Ġuntil Ġdp . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= Ġmax Of ( nums [ i ] Ġ+ Ġdp [ i Ġ- Ġ 2 ], Ġdp [ i Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġdp [ nums . size Ġ- Ġ 1 ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġhouse Rob 2 Not St abil ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . size Ġ== Ġ 1 ) Ġreturn Ġnums [ 0 ] ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . size Ġ== Ġ 2 ) Ġreturn Ġmax Of ( nums [ 0 ], Ġnums [ 1 ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( nums . size Ġ== Ġ 2 ) Ġreturn Ġmax Of ( nums [ 0 ], Ġnums [ 1 ], Ġnums [ 3 ]) ĊĠĠĠĠĠĠĠ Ġval Ġdp Ġ= ĠInt Array ( nums . size ) ĊĠĠĠĠĠĠĠ Ġdp [ 1 ] Ġ= Ġnums [ 1 ] ĊĠĠĠĠĠĠĠ Ġdp [ 2 ] Ġ= Ġmax Of ( nums [ 1 ], Ġnums [ 2 ]) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 3 Ġuntil Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= Ġmax Of ( nums [ i ] Ġ+ Ġdp [ i Ġ- Ġ 2 ], Ġdp [ i Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġmax One Ġ= Ġdp . max OrNull () Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠ Ġdp [ nums . size Ġ- Ġ 1 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġdp [ 0 ] Ġ= Ġnums [ 0 ] ĊĠĠĠĠĠĠĠ Ġdp [ 1 ] Ġ= Ġnums [ 1 ] ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 2 Ġuntil Ġnums . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ i ] Ġ= Ġmax Of ( nums [ i ] Ġ+ Ġdp [ i Ġ- Ġ 2 ], Ġdp [ i Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġmax Two Ġ= Ġdp . max OrNull () Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠ Ġreturn Ġmax Of ( max One , Ġmax Two ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġhouse Rob 2 St abil ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġdp Ġ= Ġnums . clone () ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. nums . size Ġ- Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġi Ġ+ Ġ 2 .. nums . size Ġ- Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ j ] Ġ= Ġmax Of ( dp [ j ], Ġnums [ j ] Ġ+ Ġdp [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġvar Ġmax I Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġdp . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax I Ġ= Ġmax Of ( it , Ġmax I ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprintln ( dp . content ToString ()) ĊĠĠĠĠĠĠĠ Ġdp Ġ= Ġnums . clone () ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġi Ġ+ Ġ 2 Ġuntil Ġnums . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ j ] Ġ= Ġmax Of ( dp [ j ], Ġnums [ j ] Ġ+ Ġdp [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġmax I Ġ= Ġmax Of ( dp . max OrNull () Ġas ĠInt , Ġmax I ) ĊĊĊĊĠĠĠĠĠĠĠ Ġreturn Ġmax I ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdelete And E arn ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġhash Map Ġ= ĠHashMap < Int , ĠInt >() ĊĠĠĠĠĠĠĠ Ġnums . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhash Map [ it ] Ġ= Ġhash Map . get OrDefault ( it , Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġdp Ġ= ĠInt Array ( nums . size ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠĠĠĠĠ Ġrepeat ( nums . count ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmap Ġ= Ġhash Map . clone () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdp [ it ] Ġ= Ġe arn ( map Ġas ĠHashMap < Int , ĠInt >, Ġnums [ it ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprintln ( dp . content ToString ()) ĊĠĠĠĠĠĠĠ Ġreturn Ġdp . max OrNull () Ġ?: Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġe arn ( hash Map : ĠHashMap < Int , ĠInt >, Ġvalue : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġhash Map . remove ( value Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġhash Map . remove ( value Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġhash Map [ value ] Ġ= Ġhash Map . get OrDefault ( value , Ġ 1 ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( hash Map [ value ] Ġ== Ġ 0 ) Ġhash Map . remove ( value ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( hash Map . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġvalue ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Key Ġ= Ġhash Map . keys . toList ()[ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġvalue Ġ+ Ġe arn ( hash Map , Ġfirst Key ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdelete And E arn DP ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcount Ġ= ĠInt Array ( 1 0 0 0 1 ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( x Ġin Ġnums ) Ġcount [ x ] ++ ĊĠĠĠĠĠĠĠ Ġvar Ġavoid Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġusing Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġprev Ġ= Ġ- 1 ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( k Ġin Ġ 0 .. 1 0 0 0 0 ) Ġif Ġ( count [ k ] Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġm Ġ= ĠMath . max ( avoid , Ġusing ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( k Ġ- Ġ 1 Ġ!= Ġprev ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġusing Ġ= Ġk Ġ* Ġcount [ k ] Ġ+ Ġm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġavoid Ġ= Ġm ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġusing Ġ= Ġk Ġ* Ġcount [ k ] Ġ+ Ġavoid ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġavoid Ġ= Ġm ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprev Ġ= Ġk ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġmax Of ( avoid , Ġusing ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġprintln ( Day 3 (). delete And E arn DP ( int ArrayOf ( 3 , Ġ 4 , Ġ 2 ))) Ċ }