{"version":"1.0","height":"190","width":"100%","type":"rich","author_name":"enakai00","provider_name":"Hatena Blog","provider_url":"https://hatena.blog","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F07%2F19%2F091947\" title=\"DP\u6f14\u7fd2\uff08\u554f\u984c\u6848\uff09 - \u3081\u3082\u3081\u3082\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","url":"https://enakai00.hatenablog.com/entry/2021/07/19/091947","categories":[],"title":"DP\u6f14\u7fd2\uff08\u554f\u984c\u6848\uff09","published":"2021-07-19 09:19:47","image_url":null,"author_url":"https://blog.hatena.ne.jp/enakai00/","blog_url":"https://enakai00.hatenablog.com/","blog_title":"\u3081\u3082\u3081\u3082","description":"\u30c6\u30f3\u30d7\u30ec\u30fc\u30c8\u306b\u6163\u308c\u308b\u305f\u3081\u306e\u554f\u984c \u4ee5\u4e0b\u306e\u554f\u984c\u306b\u3064\u3044\u3066\u3001DP \u306e\u30c6\u30f3\u30d7\u30ec\u30fc\u30c8\u306b\u5f93\u3063\u3066\u30b3\u30fc\u30c9\u3092\u66f8\u3044\u3066\u304f\u3060\u3055\u3044\u3002\u307e\u305f\u3001\u305d\u308c\u305e\u308c\u306e\u8a08\u7b97\u91cf\uff08 \u306a\u3069\uff09\u3092\u7b54\u3048\u3066\u304f\u3060\u3055\u3044\u3002[\u30c6\u30f3\u30d7\u30ec\u30fc\u30c8] # N: \u30c7\u30fc\u30bf\u6570 dp = [None] * (N+1) dp[1] = xxxx # 1\u500b\u306e\u5834\u5408\u306e\u7b54\u3048\u3092\u81ea\u529b\u3067\u8003\u3048\u3066\u5165\u529b\u3059\u308b for n in range(2, N+1): dp[n] = xxxxx # dp[1] ... dp[n-1] \u306e\u60c5\u5831\u3092\u4f7f\u3063\u3066 n \u500b\u306e\u5834\u5408\u306e\u7b54\u3048 dp[n] \u3092\u8a08\u7b97\u3059\u308b print(dp[N]) [\u554f\u984c1] N \u500b\u306e\u6574\u6570\u306e\u6700\u5927\u5024\u3092\u6c42\u3081\u308b [\u554f\u984c2] N \u500b\u306e\u6574\u6570\u306e\u5e73\u5747\u5024\u3092\u6c42\u3081\u308b\u30d2\u30f3\u30c8 [\u554f\u984c\u2026"}