凑零钱

给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

输入样例：
3 3
1 2 5

输出样例:
3

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

#include<bits/stdc++.h>
using namespace std;
int dp[400];
int N,M;
vector<int>v;
// 1.定义dp数组的含义
// 2.找边界解
// 3.找动态转移方程

// 该问题的思路
// 1.将dp数组定义为：当总金额为i，则dp[i]表示至少需要dp[i]枚金币
// 2.显然当总金额为0时，至少需要0枚金币，当总金额小于0时无解。
// 3.遍历所有面值的金币，当金币面值为n时，且总金额为m时，那么dp[m-n]+1(即总金额为m-n的解加1即为
// 总金额为m所需的金币数

// 自顶而下的动态规划，自顶而下求解子问题，把已求出的结果用dp数组存起来，求解释，先判断该子问题
// 是否已有解，若有解直接使用dp数组内的值。
int dfs(int n){
    if(dp[n])return dp[n];
    if(n==0)return 0;
    if(n<0)return -1;
    int res=0x3f3f3f3;
    for(int i=0;i<N;i++){
        int subproblem=dfs(n-v[i]);
        if(subproblem==-1)continue;
        dp[n-v[i]]=subproblem;
        res=min(res,subproblem+1);
    }
    return res!=-1?res:-1;
}
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        v.push_back(a);
    }
    cout<<dfs(M);
    return 0;
}

最长上升子序列

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

int dp[500],a[500];
int N;
int dfs(int s){
    if(s>=N)return -1;
    if(s==N-1)return 1;
    if(dp[s])return dp[s];
    int Max=0;
    for(int i=s+1;i<N;i++){
        if(a[i]>a[s]){
            int subproblem=dfs(i);
            if(subproblem==-1)continue;
            dp[i]=subproblem;
            Max=max(Max,subproblem);
        }
    }
    return Max+1;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<N;i++){
        ans=max(dfs(i),ans);
    }
    cout<<ans;
    return 0;
}