LeetCode 2167 - Minimum Time to Remove All Cars Containing Illegal Goods 解題心得( 題目 )
解題概念:DP
解題方法:這題首先試試greedy，雖然看似可以，但是有時得到的不是最佳解。我們定義dp[i]表示在i之前由左邊或中間管理，可以列出下列轉移式:
dp[i]=min(dp[i]+中間費用,i)
其中有兩種選擇，一種是拿中間，一種是直接從左邊拿到右邊。
最後枚舉所有從右邊到達的終點，每個解是dp[i]+n-i，從這裡面找最好的解。
Java參考程式碼(有更好解法可在下方留言，謝謝!):
//Date:2022/02/09
//Author:En Chi Tsung(欉恩祁)
class Solution {
int[] dp=new int[200005];
int min=1<<30;
public int minimumTime(String s) {
final int n=s.length();
for(int i=0;i<n;i++) {
if(s.charAt(i)=='0') {
dp[i+1]=Math.min(dp[i],i+1);
}
else {
dp[i+1]=Math.min(dp[i]+2,i+1);
}
}
for(int i=1;i<=n;i++) {
min=Math.min(dp[i]+n-i,min);
}
return min;
}
}
文章標籤
全站熱搜
