プログラミングコンテストチャレンジブック(2-3)
数字の種類と個数が幾つか与えられたときに足し算で任意の数が作れるかという問題。DPで解く
プログラミングコンテストチャレンジブック配列を0以外の数で初期化する方法が分からなかったので、初期化してから全ての要素に-1を放り込むためにループを回したけど、ここはどうするのがいいんだろう。あと本のコード間違ってるよね。dp[0]には0じゃなくてmiを入れないと。
package main import "fmt" const MAX_N = 100 func main() { n := 3 a := []int{3,5,8} m := []int{3,2,2} K := 17 dp := [MAX_N]int{} for i,_ := range(dp) { dp[i] = -1 } for i := 0; i<n; i++ { dp[0] = m[i] for j := 0;j<=K;j++ { if dp[j] >= 0 { dp[j] = m[i] } else if j < a[i] || dp[j - a[i]] <= 0 { dp[j] = -1 } else { dp[j] = dp[j - a[i]] - 1 } } } if dp[K] >= 0 { fmt.Println("yes") } else { fmt.Println("no") } }