背包问题变种

看了这么多解答，各种回溯法的确可以做，但没有写到点子上，就是一个背包问题的变种
和lintcode 上的换硬币问题是一模一样的：
https://www.lintcode.com/problem/coin-change/description

if __name__ == "__main__":
    x = int(input())
    # dp[n] 容量为 n 能够装满所需的最小个数
    a = [3, 5, 7]
    dp = [i for i in range(x+1)]
    for i in range(1, x+1):
        dp[i] = x+1
        for j in a:
            if j<=i:
                dp[i] = min(dp[i], dp[i-j] + 1)
    print(-1 if dp[x]==x+1 else dp[x])