動态規劃解鋼條切割問題

題目描述

給一條鋼管，切割成不同長度的鋼管（也可以不切割），不同的鋼管長度對應不同的價值，求這根鋼管獲得的最大價值。

輸入

第一行包含一個正整數L，為鋼管的長度。

第二行包含L個正整數a1…aL，為長度從1到L的鋼管對應的價值。

輸出

輸出一行，為鋼管能獲得的最大價值。

輸入樣例

5
1 10 14 8 16
           

輸出樣例

思考後直接想到采用自底向上的動态規劃法，即從2到n（n為鋼管長度）存入每一個長度的鋼管的最優價值，并逐漸往上（利用之前已存的資料）

下面給出完整代碼

# include <bits/stdc++.h>
using namespace std;
# define maxn 1005000
int a[maxn];
int dp[maxn];
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dp[0] = 0, dp[1] = a[1];
    for(int i = 2; i <= n; i++){
        int q = -999999999; //置q為負無窮
        for(int j = 1; j <= i; j++)
            q = max(q, dp[i - j] + a[j]); //對于長度為i的鋼材，分成兩段找最大值 
        dp[i] = q;
    }
    cout << dp[n];
    return 0；
}