AtCoder Beginner Contest 288 pE - Wish List 解題心得

AtCoder Beginner Contest 288 pE - Wish List 解題心得 ( 題目 )

<p style="margin: 1em 0px; padding: 0px; border: 0px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-weight: 400; font-stretch: inherit; font-size: 1.1rem; line-height: 1.75rem; font-family: "Noto Sans TC", 微軟正黑體, sans-serif; vertical-align: baseline; color: rgb(52, 52, 52); letter-spacing: 1px; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"> 解題概念: 2d DP

<p style="margin: 1em 0px; padding: 0px; border: 0px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-weight: 400; font-stretch: inherit; font-size: 1.1rem; line-height: 1.75rem; font-family: "Noto Sans TC", 微軟正黑體, sans-serif; vertical-align: baseline; color: rgb(52, 52, 52); letter-spacing: 1px; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"> 解題方法:這題的解題策略是利用動態規劃(DP)，發現一個性質是如果先拿掉後面的其實不會影響到前面的cost，所以我們的狀況可以定義成 dp[i][j] =做到第 i 個時的時候拿了 j 個物品，透過區間最小去選順序，求區間最小的方法用建表就可以，時間複雜度為O(N^2)。

Java solution code:

https://wtools.io/paste-code/bJ8e

阿祁的部落格

這裡為我分享程式設計心得的地方，不過因為我還不是高手，所以我寫的這些內容也許不完全正確，有好的意見也歡迎留言!!謝謝你的觀看!

AtCoder Beginner Contest 288 pE - Wish List 解題心得

個人資訊

熱門文章

文章分類

最新文章

動態訂閱

文章精選

文章搜尋

誰來我家

參觀人氣