<p>2021-02-18：給定一個字符串str命迈，給定一個字符串類型的數(shù)組arr，出現(xiàn)的字符都是小寫英文因俐。arr每一個字符串精肃，代表一張貼紙，你可以把單個字符剪開使用潜慎，目的是拼出str來捡多。返回需要至少多少張貼紙可以完成這個任務(wù)。例子：str= "babac"铐炫，arr = {"ba","c","abcd"}垒手。a + ba + c? 3? abcd + abcd 2? abcd+ba 2。所以返回2倒信。</p><p/><p>福哥答案2021-02-18：</p><p>自然智慧即可科贬。</p><p>帶記憶的遞歸。對“babac”排序鳖悠，變成“aabbc”榜掌，然后根據(jù)數(shù)組，依次消掉a乘综，然后b憎账，最后c，這是一個優(yōu)化點(diǎn)卡辰。有代碼胞皱。</p><p>代碼用golang編寫邪意，代碼如下：</p><p/><p>go</p><p>package main</p><p/><p>import (</p><p>&nbsp; &nbsp; &quot;fmt&quot;</p><p>&nbsp; &nbsp; &quot;strings&quot;</p><p>)</p><p/><p>const MAX = int(^uint(0) &gt;&gt; 1) //構(gòu)造0111111111....&nbsp; &nbsp;9223372036854775807</p><p>const MIN = int(^MAX)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //構(gòu)造10000000...&nbsp; &nbsp;-9223372036854775808</p><p>func main() {</p><p>&nbsp; &nbsp; ret := minStickers([]string{&quot;ba&quot;, &quot;c&quot;, &quot;abcd&quot;}, &quot;babac&quot;)</p><p>&nbsp; &nbsp; fmt.Println(ret)</p><p>}</p><p/><p>func minStickers(stickers []string, target string) int {</p><p>&nbsp; &nbsp; N := len(stickers)</p><p>&nbsp; &nbsp; counts := make([][]int, N)</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; counts[i] = make([]int, 26)</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; str := stickers[i]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; for _, cha := range str {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counts[i][cha-&#39;a&#39;]++</p><p>&nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; dp := make(map[string]int)</p><p>&nbsp; &nbsp; dp[&quot;&quot;] = 0</p><p>&nbsp; &nbsp; ans := process(counts, target, dp)</p><p>&nbsp; &nbsp; if ans == MAX {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return -1</p><p>&nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return ans</p><p>&nbsp; &nbsp; }</p><p>}</p><p>func process(stickers [][]int, t string, dp map[string]int) int {</p><p/><p>&nbsp; &nbsp; if _, ok := dp[t]; ok {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return dp[t]</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; tcounts := make([]int, 26)</p><p>&nbsp; &nbsp; for _, cha := range t {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; tcounts[cha-&#39;a&#39;]++</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; N := len(stickers)</p><p>&nbsp; &nbsp; min := MAX</p><p>&nbsp; &nbsp; for i := 0; i &lt; N; i++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; sticker := stickers[i]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; if sticker[t[0]-&#39;a&#39;] &gt; 0 {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; builder := strings.Builder{}</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j &lt; 26; j++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if tcounts[j] &gt; 0 {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nums := tcounts[j] - sticker[j]</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for k := 0; k &lt; nums; k++ {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; builder.WriteByte(&#39;a&#39; + byte(j))</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rest := builder.String()</p><p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = getMin(min, process(stickers, rest, dp))</p><p>&nbsp; &nbsp; &nbsp; &nbsp; }</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; ans := min</p><p>&nbsp; &nbsp; if min != MAX {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; ans++</p><p>&nbsp; &nbsp; }</p><p>&nbsp; &nbsp; dp[t] = ans</p><p>&nbsp; &nbsp; return ans</p><p>}</p><p>func getMin(a int, b int) int {</p><p>&nbsp; &nbsp; if a &lt; b {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return a</p><p>&nbsp; &nbsp; } else {</p><p>&nbsp; &nbsp; &nbsp; &nbsp; return b</p><p>&nbsp; &nbsp; }</p><p>}</p><p></p><p>執(zhí)行結(jié)果如下：</p><p class="image-package"><img class="uploaded-img" src="https://upload-images.jianshu.io/upload_images/22862325-054ab5fef8a193da.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" width="auto" height="auto"/></p><p/><p>***</p><p>左神java代碼</p><p>評論</p><p>
</p>