题解 | #汽水瓶#

本题思路：动态规划
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];
}