1884. Take Away The Bottle
class Solution {
public:
/**
* @param arr: the array of bottles
* @return: the minimum number of times you can take all the bottles
*/
int takeAwayTheBottle(vector<int> &arr) {
// Write your code here.
// search longest palidrome sub sequence.
// 居然是DP，感觉没有道理的DP.
// 看了凡是涉及substr，subseq,又是最大最小，或个数就先考虑DP。这是一个可能方向,虽然开始
// 会理不清DP的转移，但往这个方向分析，定义了状态的物理意义就可能明显些了。
// dp[i][j]: index i和j之间的最小次数。
// transition:
// 1) arr[i] == arr[j]: dp[i][j] = dp[i + 1][j - 1];
// 2) else: (往前遍历) k = j - 1,....,i: min(dp[i][k] + dp[k + 1][j]) 最小值。
// result: dp[0][size - 1];
const int size = arr.size();
if(size <= 1){
return size;
}
vector<vector<int>> dp(size, vector<int>(size, INT_MAX));
for(int i = 0; i < size; i++){
dp[i][i] = 1;
}
for(int i = size - 1; i >= 0; i--){
for(int j = i + 1; j < size; j++){
if(arr[i] == arr[j]){
dp[i][j] = (j == i + 1) ? 1 : dp[i + 1][j - 1];
}
else{
for(int k = j - 1; k >= i; k--){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][size - 1];
}
};
Comments
Post a Comment