题解 | 硬币凑钱

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int dp[]=new int[n+5];//1 5 7
		//1 2 3 4  1 2 1 2 3  2  3  2  4  5   2  3  4  5  6   2  
		//1 2 3 4  5 6 7 8 9  10 11 12 13 14  15 16 17 18 19  20
		for (int i = 1; i <= 4; i++) {
			dp[i]=i;
		}
		dp[5]=1;
		dp[6]=2;
		dp[7]=1;
		for (int i = 8; i < n+1; i++) {
			dp[i]=Math.min(dp[i-1]+1, dp[i-5]+1);
			dp[i]=Math.min(dp[i], dp[i-7]+1);
		}
		System.out.println(dp[n]);

	}

}

这题只需要考虑三种情况，求它们的最小值，如果要求dp[i]，分别求出dp[i-1]+1，dp[i-5]+1，dp[i-7]+1的值，然后求它们的最小值，这就是状态转移方程。初始化就是把dp[1]到dp[7]全部初始化赋值过去。然后这道题就做出来了