题解 | #汽水瓶#
汽水瓶
http://www.nowcoder.com/practice/fe298c55694f4ed39e256170ff2c205f
本题思路：动态规划
1.确定动态数组及下标含义
dp[i]：表示有i个汽水瓶瓶最多能和dp[i]瓶汽水
2.确定动态方程
dp[i] = max(dp[i], dp[j] + dp[i - j])
3.确定初始化条件
dp[1] = 0;
dp[2] = 1;
dp[0]是没有意义的值
4.确定遍历方向
从前往后遍历
#include<iostream>
#include<vector>
using namespace std;
int getSadaWater(int n);
int main(){
int num;
while(cin >> num){
if(num == 0)
break;
cout << getSadaWater(num) << endl;
}
return 0;
}
int getSadaWater(int n){ //动态规划
if(n == 1)
return 0;
vector<int> dp(n + 1, 0);
dp[2] = 1;
for(int i = 3; i < dp.size(); ++i){
for(int j = 1; j <= i / 2; ++j){
dp[i] = max(dp[i], dp[j] + dp[i - j]);
}
}
return dp[n];
}
