华为面试题求解析

动态规划，num[n] = min(num[n-4], num[n-9]) + 1, num[n]是装n个钉子需要的最少盒数

import java.util.Scanner; public class Main1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); int min = -1; for (int i = n/9; i >=0 ; i--) { if((n-9*i)%4==0) { min=i+(n-9*i)/4; break; } } System.out.println(min); } }

4x+9y=m x+y=n 欲令n最小： 4x+4y=4n,5y=m-4n,5x=9n-m 说白了就是先找最小的n使得m和4n关于5同余嘛，n%5==-m%5 最后记得检验一下x和y的正负关系就行了，有负的话n就调个5看看

#include <iostream> #include <vector> using namespace std; class Solution { public: int buyNails(vector<int>& nails, int count) { vector<int> dp(count + 1, -1); dp[0] = 0; for (int i = 1; i <= count; i++) { for (int j = 0; j < nails.size(); j++) { if (i - nails[j] >= 0 && dp[i - nails[j]] != -1) { if (dp[i] == -1 || dp[i] > dp[i - nails[j]] + 1) dp[i] = dp[i - nails[j]] + 1; } } } return dp[count]; } }; int main() { vector<int> nails = { 4, 9 }; int n; cin >> n; Solution s; cout << s.buyNails(nails, n) << endl;; return 0; }

leetcode换零钱吧，这题比那个还简单一点

DP换硬币问题

不用知道什么方法，直接除就好

我当时没想到动态规划，用的广度优先搜索做的。这可以理解为一个无权图求最短路径的问题，不就是广度优先搜索嘛，用队列实现，同时避免重复访问。

有点像辗转相除法

简单dp

贪心回溯或者动态规划都可以。动态规划可以参考leetcode322题。

a=n%9 b=a%4 如果b为1，拆3个9来补整； 如果b为2，拆2个； 如果b为3，拆3个。

动态规划

背包问题扩展，自己好好想想吧

暴力破解

贪心就行了

贪心回溯，或者简单点，用数学公式直接算出来