在钢管切割的背景下，已经知道长度为1−n的钢管的价值，给定长度为n的钢管在切割若干次（也可以不切割）所带来的最小价值是？
多组数据输入
第一行一个整数n，为起始钢管长度（0<n≤1000）
第二行n个整数，分别为长度为i的钢管的价值ti（0<ti≤10^6）
对于每组数据，输出一行，为这根钢管所带来的最小价值T
3 2 3 7
5
算法导论第三版15.1节
dp[i] = min(dp[i-j] + dp[j], dp[i]);
#include <iostream> #include <stdio.h> using namespace std; long long n,dp[1003]; int main() { while(~scanf("%d",&n)) { for(int i = 1; i <= n; i++) { scanf("%d",&dp[i]); } for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) dp[i] = min(dp[i-j] + dp[j], dp[i]); printf("%d\n",dp[n]); } return 0; }
原文：https://www.cnblogs.com/kubab119/p/11823254.html