LeetCode 691. 貼紙拼詞

我們有 n 種不同的貼紙。每個貼紙上都有一個小寫的英文單詞。

您想要拼寫出給定的字符串 target ，方法是從收集的貼紙中切割單個字母并重新排列它們。如果你愿意，你可以多次使用每個貼紙，每個貼紙的數(shù)量是無限的。

返回你需要拼出 target 的最小貼紙數(shù)量。如果任務(wù)不可能，則返回 -1 。

注意：在所有的測試用例中，所有的單詞都是從 1000 個最常見的美國英語單詞中隨機(jī)選擇的，并且 target 被選擇為兩個隨機(jī)單詞的連接。

動態(tài)規(guī)劃，狀態(tài)壓縮，記憶化搜索......其實(shí)這些東西我應(yīng)該是掌握了的，我以為自己已經(jīng)通過上次的題目掌握了，結(jié)果到需要用的時候還是......

分析一下原因吧，還是因?yàn)闆]有理解動態(tài)規(guī)劃的本質(zhì)，只會復(fù)讀什么“分解成子問題”。

根本的根本問題是，抽象思維能力差太多。哪怕看了官方題解，還是有一堆問題：

首先最大的問題是，所有給res賦值的語句里，沒有值低于m+1的，但是為什么最后還是能夠返回那么小的值，那些值是從哪來的......

很神奇吧，沒有任何一條語句給res賦值3，但是最后它就是可以等于3。

直接說結(jié)論：res的值是從memo[0]獲取的。

假設(shè)可以拼出來，那么第一次真正有返回值的回調(diào)，mask一定是全0，也就是memo[0]=0。

或者說的專業(yè)一點(diǎn)，res的值是由狀態(tài)memo[0]轉(zhuǎn)移而來的。

程序是過程，是動態(tài)的，而我總是用靜態(tài)的方法去思考，所以像個傻逼。對于簡單的問題，確實(shí)可以這樣，但過于抽象的問題就必須以動態(tài)的思維來看。

......

其實(shí)細(xì)節(jié)部分諸如位運(yùn)算，還有if的條件之類的，很好理解，我真正覺得難以理解的是整體的思維?；蛘哒f，該怎么去思考一個問題......

分解成子問題，我也會這樣想，也想到了狀態(tài)壓縮，但是真正去把這些東西優(yōu)雅地組合起來解決問題，腦子就亂了。如果題目改成每次只能從貼紙中選一個字母，那我大概就行了，就是單純地復(fù)雜了一個維度，我就很難把這個新的維度和已有的解題思路組合起來。

對于這題而言，我一直是存在誤區(qū)的：

1. 從貼紙中尋找多個字符，或者單個字符，其實(shí)是同一個問題，但是我從來沒有這么想過。我想到了算target和貼紙的重合部分，但是我是這么想的：尋找單個字符循環(huán)一次，尋找兩個再循環(huán)，三個再循環(huán)，直接找不到，選出最大重合部分的貼紙，再尋找剩下的部分。

   這種時候動態(tài)規(guī)劃的優(yōu)勢是，可以讓人頭腦清晰。我按自己的思路很快就被一堆亂七八糟的東西堵住了，但動態(tài)規(guī)劃提供了一個可靠的框架，只要在框架里搭上正確的積木就行。

   還是那個問題，我的思維依舊不夠抽象。

2. 貼紙的字符的順序是可以不去關(guān)心的。因?yàn)橐阒睾喜糠?，我就覺得貼紙的字符的順序也必須要和target一樣。

   但其實(shí)沒有，根本不用去在意順序，真正應(yīng)該關(guān)心的是一張貼紙里能夠找到的和target相同的字符數(shù)量，順序無關(guān)緊要，我沒有意識到這一點(diǎn)，所以想不出來。

   所以我還缺少看透問題本質(zhì)的能力。

3. 留空?？赡苁沁f歸寫的少了，我完全不習(xí)慣先把返回值交給下一次調(diào)用這個思考方式，要讓這個函數(shù)能夠適配每一次的調(diào)用還要在最后返回正確的結(jié)果，該怎么做完全是空白。、

總結(jié)：四天沒想出結(jié)果直接看了題解，下次遇到一樣的問題大概還是沒有頭緒。

但至少總結(jié)出了一些方向，不算完全沒有價值。