[数据结构与算法]洛谷P1164 小A点菜 dp

刚开始看感觉就是到普通的dfs
直到我无视了作者的时间强调tle了一半之后
这个dfs是优化后的,即便是过了前面的点但还是tle了最后一个,推测是极限情况下钱数足够把所有的菜都点一遍.

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

const int N = 1005;

int n,m;
int ans;
int a[N];
void dfs(int x,int y)
{
    if(!x)
        ans++;
    else if(y == n + 1)
        return;
    else
    {
        if(x - a[y] >= 0)
            dfs(x - a[y],y + 1);
        dfs(x,y + 1);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    dfs(m,1);
    cout << ans;
    
    return 0;
}

然后就是作者应该希望用的dp写法了.

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

const int N = 10005;

int n,m;
int ans[105][N];//前i道菜用光j块钱的方法总数
int a[105];

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    for(int i = 0 ; i <= n ; i++)
        ans[i][0] = 1;//初始化状态
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            //对于同一道菜有两种选择:吃或不吃
            if(a[i] > j)//吃的前提是钱数足够,钱不够直接告辞下一道
                ans[i][j] = ans[i - 1][j];
            else//否则既可以吃也可以不吃
                ans[i][j] = ans[i - 1][j] + ans[i - 1][j - a[i]];
        }
    cout << ans[n][m];
    
    return 0;
}