{"title":"\u4eca\u65e5\u89e3\u3044\u305f\u554f\u984c","provider_url":"https://hatena.blog","categories":["Ruby","\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0"],"version":"1.0","author_name":"ganmacs","author_url":"https://blog.hatena.ne.jp/ganmacs/","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fganmacs.hatenablog.com%2Fentry%2F2014%2F08%2F03%2F000118\" title=\"\u4eca\u65e5\u89e3\u3044\u305f\u554f\u984c - memo-mode\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","blog_url":"https://ganmacs.hatenablog.com/","blog_title":"memo-mode","published":"2014-08-03 00:01:18","width":"100%","height":"190","description":"\u5206\u5272\u6570\u306f\u3044\u307e\u3044\u3061\u308f\u304b\u3063\u3066\u3044\u306a\u3044 \u6700\u9577\u5897\u52a0\u90e8\u5206\u5217\u554f\u984c \u81ea\u5206(i)\u3088\u308a\u5c0f\u3055\u3044\u90e8\u5206\u554f\u984c\u3092\u89e3\u3044\u3066\u3044\u3051\u3070\u3067\u304d\u308b 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 \u5206\u5272\u6570 N\u3092M\u500b\u4ee5\u4e0b\u306b\u5206\u5272\u3059\u308b\u7dcf\u6570 N=4,M=3\u306e\u5834\u5408 dp(3,4)=dp(3,1)+dp(2,4)\u306b\u306a\u308b\uff0e dp(2,4)\u306f\u7dcf\u6570\u306a\u306e\u3067\u2026","provider_name":"Hatena Blog","image_url":null,"url":"https://ganmacs.hatenablog.com/entry/2014/08/03/000118","type":"rich"}