隐性的DP题目类型
居然是DP，感觉没有道理的DP.
// 看了凡是涉及substr，subseq,又是最大最小，或个数就先考虑DP。这是一个可能方向,虽然开始 // 会理不清DP的转移，但往这个方向分析，定义了状态的物理意义就可能明显些了。
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];
}
};
// 看了凡是涉及substr，subseq,又是最大最小，或个数就先考虑DP。这是一个可能方向,虽然开始 // 会理不清DP的转移，但往这个方向分析，定义了状态的物理意义就可能明显些了。
1884. Take Away The Bottle
There are
that form a continuous substring of the palindrome and take them away,
and then stitch the remaining bottles together in the original order.
Return the minimum number of times you can take all the bottles.
n bottles in a row, represented byarr. Each time you can choose the bottlesthat form a continuous substring of the palindrome and take them away,
and then stitch the remaining bottles together in the original order.
Return the minimum number of times you can take all the bottles.
n<=500
arr[i]<=1000
arr[i]<=1000
Have you met this question in a real interview?
Example
Example1:
Input：[1,3,4,1,5]
Output：3
Explanation：Take [4] for the first time, remaining [1,3,1,5]
Take away [1,3,1] for the second time, remaining [5]
Take away [5] for the third time
Example2:
Input：[1,2,3,5,3,1]
Output：2
Comments
Post a Comment