经典完全背包问题

  • 首先确定背包的遍历顺序直接从外层遍历是物品,里面遍历背包
  • 注意是完全背包,一阶dp数组要正向遍历
  • 最后注意边界问题
    ``` java
    import java.util.*;
    public class Solution {
    public int minMoney (int[] arr, int aim){
          int  []dp=new int[aim+1];
          Arrays.fill(dp,aim+1);// 初始化最大值的时候直接选取
          int n=arr.length;
          dp[0]=0;//初始状态
        for(int a:arr){
              for(int   j=1;j<=aim;j++){
                    if(j>=a){
                         dp[j]=Math.min(dp[j], dp[j - a] + 1);
                    }
              }
        }
         return    dp[aim]==aim+1?-1:dp[aim];
    }
    }