Burst Balloons: omvänd intervall-DP

Givet n ballonger med värdena nums ger det nums[i-1] * nums[i] * nums[i+1] mynt att spräcka ballong i (produkten av dess värde och de aktuella grannarnas värden). När den spricker blir grannarna intilliggande. Hitta det maximala antalet mynt ni kan samla genom att spräcka alla ballonger. Den naiva simuleringen är svår eftersom grannarna förändras när ballonger spricker — omvänd intervall-DP kringgår elegant denna svårighet.

Om vi försöker definiera dp[i][j] som det maximala antalet mynt från att spräcka ballongerna i intervallet [i, j] och funderar på vilken ballong som ska spräckas först, uppstår ett problem: att spräcka ballong k först innebär att nums[k-1] och nums[k+1] måste vara de aktuella grannarna — men de ballongerna kanske spräcks senare, vilket förändrar grannarna dynamiskt. Tillståndet är svårt att definiera på ett tydligt sätt i framåtriktningen.

Tricket är att tänka på vilken ballong som spräcks sist i intervallet [i, j]. När ballong k är den sista som spräcks i [i, j] är alla andra ballonger i [i, j] redan borta. Därför är grannarna till ballong k exakt nums[i-1] och nums[j+1] — gränsballongerna precis utanför intervallet. Detta gör myntberäkningen för den sista spräckningen deterministisk: den beror inte på ordningen för tidigare spräckningar.

Lägg till sentinelballonger: lägg till och infoga 1 i början och slutet av nums för att bilda nums = [1] + nums + [1]. Definiera dp[i][j] som det maximala antalet mynt från att spräcka alla ballonger strikt mellan index i och j (exklusivt), där nums[i] och nums[j] är de kvarvarande gränsballongerna. Rekurrens: för varje möjlig sista ballong k i (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Vi fyller ut arrayen med sentinelvärden, initierar DP-tabellen till noll (tomt intervall = 0 mynt) och fyller tabellen efter stigande intervallängd. Det slutliga svaret är dp[0][n+1], vilket representerar det maximala antalet mynt från att spräcka alla ursprungliga ballonger med sentinelvärdena som permanenta gränser.

För [3, 1, 5, 8], utfylld till [1, 3, 1, 5, 8, 1] (index 0–5). Vi vill ha dp[0][5]. För intervall med längden 2 (en ballong inuti): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. När vi bygger upp lösningen är det optimalt att spräcka 1 sist bland {3,1,5,8}, efter att först ha spräckt grannarna, vilket ger totalt 167 mynt.

Det finns O(n²) intervall, och för varje intervall provar vi O(n) delningspunkter, vilket ger O(n³) tidskomplexitet. Minnesanvändningen är O(n²) för DP-tabellen. För n = 500 ballonger innebär detta 125 miljoner operationer — genomförbart med intervjukraven. Utfyllnaden med sentinelvärden förenklar hanteringen av gränser: utan den skulle ni behöva uttryckliga kontroller av om i-1 och j+1 ligger inom gränserna.

Samma lösning kan skrivas top-down med @lru_cache, vilket kan vara mer intuitivt att härleda under en intervju. Definiera solve(i, j) som det maximala antalet mynt i det öppna intervallet (i, j). Funktionen provar alla k som den sista ballongen som spräcks och memoiserar resultaten. Båda metoderna har identisk tids- och minneskomplexitet.

Ett vanligt misstag är att definiera dp[i][j] som antalet mynt när den första ballongen i [i,j] spräcks, i stället för den sista. Detta misslyckas eftersom myntberäkningen för den första spräckningen beror på grannballonger som ännu inte har spräckts — och deras tillstånd förändras när algoritmen fortsätter. Tänk alltid på det sista elementet i intervall-DP när gränserna beror på de element som finns kvar.

Sentinelvärden på 1 väljs eftersom de fungerar som neutrala element för multiplikation. När en gränsballong är den sista som spräcks blir dess myntvärde boundary * last * boundary = 1 * last * 1 = last. Om ni använder 0 blir resultatet 0 mynt (fel), och andra värden skulle förvränga beräkningen. Tricket med sentinelvärden förenar alla gränsfall på ett tydligt sätt utan särskild hantering av den vänstraste och högra ballongen.

I standardmässig intervall-DP (matrix chain) representerar delningspunkten k var vi delar upp problemet i två delproblem som löses oberoende av varandra. I Burst Balloons är k den sista ballongen som spräcks i intervallet, vilket gör delintervallen [i,k] och [k,j] oberoende när k fortfarande finns kvar som gräns. Detta omvända perspektiv är den kreativa insikten som gör att Burst Balloons kan lösas med intervall-DP.

I den här lektionen har ni lärt er: framåtsimulering misslyckas eftersom när ballonger sprängs förändras grannarna på ett oförutsägbart sätt, den omvända observationen definierar k som den sista ballongen som sprängs i ett intervall, vilket gör grannarna till nums[i] och nums[j], och rekurrensen dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) med sentinelutfyllnad ger en lösning i O(n³). Härnäst går vi över till DP för ryggsäcksproblem, med början i det klassiska 0/1-ryggsäcksproblemet och dess minnesoptimering.