题目地址：

https://www.lintcode.com/problem/backpack-x/description

假设一个人手里有$n$元，他要去一个商店买价格分别是$150,250,350$的商品，商品有无限多。问他最少可以剩下多少钱。

思路是动态规划。不妨设商品价格可以由数组$A$来表示。设$f[i]$是手里有$i$元的情况下去买东西，所能剩下的最少的钱数。那么所有买商品的方案可以按照最后一个商品买了哪个来分类，注意，不买任何商品也是一种方案。所以有$$f[i]=\underset{i\ge A[j]}{\min }\{i,f[i-A[j]]\}$$代码如下：

public class Solution { /** * @param n: the money you have * @return: the minimum money you have to give */ public int backPackX(int n) { // write your code here int[] A = {150, 250, 350}; int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = i; for (int j = 0; j < A.length; j++) { if (i >= A[j]) { dp[i] = Math.min(dp[i], dp[i - A[j]]); } } } return dp[n]; } }

时间复杂度$O(n)$。