动态规划 背包 百炼-2755 神奇的口袋

题目链接：[ HDU - 2069 ]

题目大意

背包问题

思路

设V(m,n)表示在n个数字中插入m个加号所能形成 的表达式最小值，那么:

 if m = 0  
    V(m,n) = n个数字构成的整数  
 else if n < m + 1  
    V(m,n) = ∞  
 else  
    V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m ... n-1)  

Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操 作复杂度是 $O(j-i+1)$ ，可以预处理后存起来。
总时间复杂度: $O(mn^2)$

题解代码

#include<bits/stdc++.h>
using namespace std;

int dp[50][50];
int a[50];

int main(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++)
        dp[0][i] = 1;

    dp[0][0] = 1;
    for (int i = 1; i <= 40; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            if (i - a[j] >= 0)
                dp[i][j] += dp[i - a[j]][j - 1];
        }
    }

    cout << dp[40][n] << endl;
    return 0;
}