読者です 読者をやめる 読者になる 読者になる

今日解いた問題

ruby アルゴリズム

分割数はいまいちわかっていない

最長増加部分列問題

自分(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