3138: 动态规划进阶题目之货币面值

思路：既然说叫用动态规划做，那就得往动态规划方面想。
自己想的方法不是用动态规划做的，也AC了。但是还是得往动态规划上靠。
输入n，有n个面值的钱，还要有一个不能表示的最小钱数，其实应该想到dp数组的雏形了：dp[i][j]表示考虑前i个纸币，在面值总和不超过j的情况下能表示的最大面值（为什么要这样想，为什么是面值总和不超过j情况下这么别扭呢？考虑01背包问题，就是考虑前i个物品，在背包容量不超过j的情况下能放的最大价值。）。这个地方其实是一个恰好装满背包容量的01背包变式题，其实就是所装入的价值恰好等于背包容量的情况。即dp[i][j]=j 简化成一维的就是dp[i]=i dp[i]表示总钱数和不超过i时能表示的最大钱数。背包容量为多少，就恰好装满多少钱的情况。
为啥是恰好装满的01背包再好好理解理解

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10000;
int a[N],dp[N];
int main(){int n;while(~scanf("%d",&n)){memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){for(int j=N;j>=a[i];j--){dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}}for(int j=1;j<=N;j++)if(dp[j]!=j){cout<<j<<endl;break;}}
}