小A点菜（洛谷P1164题题解，Java语言描述）

题目要求

题目链接

分析

用 D P DP DP做是必然的，讲讲二维的吧： f [ i ] [ j ] f[i][j] f[i][j]：用前 i i i道菜用光 j j j元钱的可能组合数 剩下的钱等于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] + 1 f[i][j]=f[i-1][j]+1 f[i][j]=f[i−1][j]+1 剩下的钱大于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − v [ i ] ] f[i][j]=f[i-1][j]+f[i-1][j-v[i]] f[i][j]=f[i−1][j]+f[i−1][j−v[i]] 剩下的钱小于第 i i i道菜的价格时， f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]

可以压缩为一维 D P DP DP： f [ j ] + = f [ j − v [ i ] ] f[j]+=f[j-v[i]] f[j]+=f[j−v[i]] 解读为：当前花费情况下的点菜可能数，对于每道菜，包含点这个菜和不点这个菜的两种可能数之和。

AC代码（Java语言描述）

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i = i; j--) {
                result[j] += result[j-i];
            }
        }
        System.out.println(result[m]);
    }
}