{"width":"100%","blog_title":"\u571f\u4e0b\u5ea7\u3057\u306a\u304c\u3089\u63a2\u7d22\u4e2d","description":"\u554f\u984c\u30ea\u30f3\u30af\uff1aMaximum Sum\u554f\u984c\u6982\u8981\uff1a N*N\u306e2\u6b21\u5143\u914d\u5217\u304c\u4e0e\u3048\u3089\u308c\u308b \u3053\u306e\u4e2d\u304b\u3089\u4f5c\u308c\u308b\u9577\u65b9\u5f62\u306e\u3046\u3061\u305d\u306e\u8981\u7d20\u306e\u548c\u304c\u6700\u5927\u306e\u3082\u306e\u3092\u307f\u3064\u3051\u3088\u89e3\u6cd5\uff1a \u3088\u304f\u3042\u308bDP memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]\u3068\u3044\u3046\u914d\u5217\u3092\u7528\u610f\u3059\u308b array\u306f\u5165\u529b\u3067\u4e0e\u3048\u3089\u308c\u308b2\u6b21\u5143\u914d\u5217 memo\u306f(0,0)\u304b\u3089(x,y)\u307e\u3067\u306e\u9577\u65b9\u5f62\u306e\u8981\u7d20\u306e\u548c\u3092\u8868\u3059\u5f8c\u306f\u9577\u65b9\u5f62\u306e\u5de6\u4e0a\u3068\u53f3\u4e0b\u3092\u30eb\u30fc\u30d7\u3067\u6c7a\u3081\u3066\u3001memo\u3092\u4ee5\u4e0b\u306e\u69d8\u306b\u5229\u7528\u3057\u3066\u9762\u7a4d\u3092\u6c42\u3081\u308b \u5de6\u4e0a\u3092(x1,y1),\u53f3\u4e0b\u3092(x2,y2)\u3068\u3059\u308b \u3053\u306e\u9577\u65b9\u5f62\u306e\u8981\u7d20\u306e\u548c\u3092S\u3068\u3059\u308b S =\u2026","height":"190","provider_url":"https://hatena.blog","provider_name":"Hatena Blog","title":" UVa 108 : Maximum Sum ","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fncastar.hatenablog.com%2Fentry%2F20131122%2F1385136232\" title=\" UVa 108 : Maximum Sum  - \u571f\u4e0b\u5ea7\u3057\u306a\u304c\u3089\u63a2\u7d22\u4e2d\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","categories":["UVa","\u52d5\u7684\u8a08\u753b\u6cd5"],"image_url":null,"type":"rich","author_url":"https://blog.hatena.ne.jp/tei3344/","author_name":"tei3344","url":"https://ncastar.hatenablog.com/entry/20131122/1385136232","published":"2013-11-22 01:03:52","blog_url":"https://ncastar.hatenablog.com/","version":"1.0"}