1175. prime number arrangement / Sword finger offer II 104 Number of permutations

1175. Permutation of prime numbers 【 Simple questions 】【 A daily topic 】

Ideas ：

Find the number of prime numbers k1,n-k1 Find the number of non prime numbers k2, Then the number of types meeting the requirements is k1 The factorial * k2 The factorial , Because the result of the operation may be out of bounds , Therefore, according to the meaning of the question, the result is 10^9+7 model .
set up MOD = 10^9+7, Therefore, the result of the above operation can be expressed as ：

ans = (k1! * k2!) % MOD

Because the factorial operation may be out of bounds , Therefore, the above formula is mathematically transformed

ans = (k1! * k2!) % MOD
	= ((k1! % MOD) * (K2! % MOD)) % MOD
	//【】 Indicates cumulative multiplication 
	= ((【k1i % MOD】 % MOD ) * (【k2i % MOD】 % MOD ) ) % MOD
	= (【k1i % MOD】 * 【k2i % MOD】) % MOD

Code ：

class Solution {
    
    static int MOD = (int) 1e9+7;
    public int numPrimeArrangements(int n) {
    
        if (n <= 2){
    
            return 1;
        }
        int k1 = 1;
        for (int i = 3; i <= n; i++) {
    
            if (isPrime(i)){
    
                k1++;
            }
        }
        int k2 = n - k1;
        long ans = 1;
        for (int i = 2; i <= k1; i++) {
    
            ans = ans * i % MOD;
        }
        for (int i = 2; i <= k2; i++) {
    
            ans = ans * i % MOD;
        }
        return (int) (ans);
    }
    public boolean isPrime(int n){
    
        int k = (int) Math.sqrt(n);
        for (int i = 2; i <= k ; i++) {
    
            if (n % i == 0){
    
                return false;
            }
        }
        return true;
    }
}

---

The finger of the sword Offer II 104. Number of permutations 【 Medium question 】

Ideas ：【 Dynamic programming 】

I was cheated by the complete knapsack formula I recited yesterday ~, This is not a knapsack problem

Code ：

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        // Definition dp Array ,dp[i] Express and for i The combination number of 
        int[] dp = new int[target+1];
        // The boundary conditions  i = 0 when , And for 0 There is only one combination of   Select no element , therefore dp[0] = 1
        dp[0] = 1;
        // Transfer equation 
        for (int i = 1; i <= target; i++) {
    
            for (int num : nums) {
    
                // Traverse nums Array , If the target and i Is greater than or equal to the current element value num, Explain that this element can be selected dp[i] The value of is equal to all that satisfy the in the array i>=num Of dp Sum of values 
                if (i >= num) {
    
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}