今日解いた問題
分割数はいまいちわかっていない
最長増加部分列問題
自分(i)より小さい部分問題を解いていけばできる
N = 5 A = [4, 2, 3, 1, 5].freeze $dp = Array.new(N, 1) def solve N.times do |i| i.times do |j| $dp[i] = [$dp[j] + 1, $dp[i]].max if A[i] > A[j] end end $dp.max end p solve # => 3
分割数
NをM個以下に分割する総数
N=4,M=3の場合
dp(3,4)=dp(3,1)+dp(2,4)
になる.
dp(2,4)
は総数なので2個以下で分割するときの総数($dp[i-1][j]
)
dp(3,1)
は3分割したもののそれぞれから1引いてそれを分割する総数($dp[i][j-1]
この場合 j < iなので0)
3分割したものから1引くとは4=1+1+2
となるのでそれぞれから1引いて0+0+1=1
N = 4 M = 3 $dp = Array.new(M + 1).map { Array.new(N + 1, 0) } def solve $dp[0][0] = 1 (1..M).each do |i| (0..N).each do |j| a = j - i >= 0 ? $dp[i][j-i] : 0 $dp[i][j] = $dp[i-1][j] + a end end $dp[M][N] end p solve # => 4