java ：动态规划

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashMap<Integer,Boolean> hash = new HashMap<>();
        int n = sc.nextInt(), sum = sc.nextInt();
        int[] W = new int[n];
        for(int i = 0; i < n; i++){
            W[i] = sc.nextInt();
        }
        int[] dp = new int[sum+1];
        dp[0] = 1;
        for (int Wi : W){
            for (int i = 0; i + Wi <= sum; i++) {
                dp[i+Wi] = dp[i+Wi]+dp[i];
            }
        }
        System.out.println(dp[sum]);
    }
}

记忆化搜索

import java.util.Scanner;

public class Main{
    static int[][] temp = new int[1020][100];//缓存数组
    static int[] arr;
    static int n;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int money = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        int res = 0;
        //money == 0 那肯定0种方案, 不用找了
        if(money != 0){
            res = dp(money, 0);
        }
        System.out.println(res);
    }
    public static int dp(int con, int index){
        if(con < 0 ) return 0; //如果当前需要找的钱变为负数了,说明这种找法不行(有0种组合),返回0;

        //找零成功返回1种组合
        if(con == 0) return 1;
        //如果以前计算过当前场面的状况, 直接返回以前计算的结果(防止重复计算)
        if(temp[con][index] != 0) return temp[con][index];
        int res = 0;
        //i从index开始,因为i以前的可能都尝试过了
        //不断找出用i以及i以后的面额找零当前的面额有多少种
        for(int i = index; i < arr.length; i++){
            if(arr[i] == 0) continue;//防止有捣乱的0元(那直接无限递归了)
            res += dp(con - arr[i], i);//用arr[i]的钱去找零
        }
        //存储在temp数组中
        temp[con][index] = res;
        return res;
    }
}

力扣518原题

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include<map>
#include<set>
using namespace std;
const int MOD = 1e9 + 7;
long long ans=0;
const int MX=100000;
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (int& coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
return 0;
}
int main()
{
int n,m;cin>>n>>m;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<change(m,a)<<endl;

return 0;

}

经典动态规划

def count_ways(coins, m):
    dp = [0 for i in range(m + 1)]
    dp[0] = 1
    for coin in coins:
        for i in range(coin, m + 1):
            dp[i] += dp[i - coin]
    return dp[m]
n, m = map(int, input().split())
coins = [int(input()) for i in range(n)]
ways = count_ways(coins, m)
print(ways)

动态规划是正向计算的，我们不妨先试试逆向理解 或者按照代码推演一遍