题解 | 买橘子

由爬楼梯转化的一个基础dp问题，可以买6个一袋也可以买8个一袋，设f(n)代表买n个橘子至少需要的袋数，则转移方程为：

f(n) = 1+min(f(n-6), f(n-8))，当然f(n-6), f(n-8)都为-1（不满足条件）时，另加讨论。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int dp[100005];
    for (int i = 0; i <= 8; ++i) {
        dp[i] = -1;
    }
    dp[6] = dp[8] = 1;
    for (int i = 9; i <= n; ++i) {
        int a = dp[i - 6];
        int b = dp[i - 8];
        if (a == -1 && b == -1) {
            dp[i] = -1;
        }
        else if (a == -1) {
            dp[i] = 1 + b;
        }
        else if (b == -1) {
            dp[i] = 1 + a;
        }
        else dp[i] = 1 + min(a, b);
    }
    cout << dp[n];
    return 0;
}