Skip to content

Latest commit

 

History

History
256 lines (254 loc) · 7.02 KB

基础算法——整数划分.md

File metadata and controls

256 lines (254 loc) · 7.02 KB

DFS＆DP https://blog.csdn.net/zcz5566719/article/details/105168494 https://blog.csdn.net/u011426016/article/details/86566416

不可重复使用求方案数

DFS（n超级大容易超时和爆空间）

Sum of Fibonacci

当前n-1项和<cur时不可能凑出来剪枝（sum[i]表示num[0...i-1]的和）

#include <bits/stdc++.h>
using namespace std;
const int N=40;
int f[N],n,sum[N],cnt=0;
void init(){
    f[0] = f[1] = 1;
    for(int i = 2; i < N; i ++) f[i] = f[i - 1] + f[i - 2];
    for(int i=1;i<N;++i){
        sum[i]=sum[i-1]+f[i];
    }
}
void dfs(int idx,int cur){
    if(cur==0){
		cnt++;
		return;
	}
    if(sum[idx]<cur||idx<=0||cur<0)return;
    //while(f[idx]>cur)idx--;
    dfs(idx-1,cur-f[idx]);
	dfs(idx-1,cur);
}
int main(){
    init();
    while(cin>>n){
		cnt=0;
		dfs(38,n);
        cout<<cnt<<endl;
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=40;
int f[N],n,sum[N];
void init(){
    f[0] = f[1] = 1;
    for(int i = 2; i < N; i ++) f[i] = f[i - 1] + f[i - 2];
    for(int i=1;i<N;++i){
        sum[i]=sum[i-1]+f[i];
    }
}
int dfs(int idx,int cur){
    if(cur==0)return 1;
    if(sum[idx]<cur||idx<=0||cur<0)return 0;
    //while(f[idx]>cur)idx--;
    return dfs(idx-1,cur-f[idx])+dfs(idx-1,cur);
}
int main(){
    init();
    while(cin>>n){
        cout<<dfs(38,n)<<endl;
    }
    return 0;
}

不用前缀和剪枝的超时版本

#include <bits/stdc++.h>
using namespace std;
const int N=40;
int f[N],n,sum[N],cnt=0;
void init(){
    f[0] = f[1] = 1;
    for(int i = 2; i < N; i ++) f[i] = f[i - 1] + f[i - 2];
    for(int i=1;i<N;++i){
        sum[i]=sum[i-1]+f[i];
    }
}
void dfs(int idx,int cur){
    if(cur==0){
		cnt++;
		return;
	}
    //if(sum[idx]<cur||idx<0||cur<0)return;
    if(idx<=0||cur<0)return;
    while(f[idx]>cur)idx--;
    dfs(idx-1,cur-f[idx]);
	dfs(idx-1,cur);
}
int main(){
    init();
    while(cin>>n){
		cnt=0;
		dfs(38,n);
        cout<<cnt<<endl;
    }
    return 0;
}

01背包

dp[0][0]=1;
for(int i=1;i<=nums.size();++i){
    dp[i][j]=dp[i-1][j];
    for(int j=0;j<=target;++j){
        if(j>=nums[i-1])dp[i][j]+=dp[i-1][j-num[i-1]];
    }
}
cout<<dp[nums.size()][target];

可重复使用求方案数

完全背包

377. 组合总和 Ⅳ组成相同顺序不同被视为不同方案

组合数：背包在外，物品在内

    int combinationSum4(vector<int>& nums, int target) {
        vector<int>dp(target+1,0);
        dp[0]=1;
        for(int i=1;i<=target;++i){
            for(int j=0;j<nums.size();++j){
                if(i>=nums[j]&&dp[i]<INT_MAX-dp[i-nums[j]]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }

518. 零钱兑换 II不同方案元素组成必须不同

排列数：物品在外，背包在内

    int change(int amount, vector<int>& coins) {
        vector<vector<int>>dp(coins.size()+1,vector<int>(amount+1,0));
        dp[0][0]=1;//没有零钱，也没有需要兑换的钱，所以方案只有一种
        for(int i=1;i<=coins.size();++i){
            for(int j=0;j<=amount;++j){
                dp[i][j]=dp[i-1][j];
                if(j>=coins[i-1]){
                    dp[i][j]+=dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[coins.size()][amount];
    }

不可重复使用具体方案

只能dfs 若元素集有重复，还需要在元素集中去重

元素集中的元素不能重复使用，但元素集中本身有重复的

40. 组合总和 II

只有当i==idx或者nums[i-1]！=nums[i]才能进入dfs i==idx使得元素集中的重复元素出现次数与重复次数一致 nums[i-1]！=nums[i]使得重复元素不会乱出现 比如说[2,5,2,1,2]的2最多出现3次，不会随意出现，不会出现任意多次

class Solution {
public:
    vector<vector<int>> ans;
    set<int>st;
    vector<int>path;
    void dfs(vector<int>&nums,int idx,int target){
        if(target==0){
            ans.push_back(path);
            return;
        }
        for(int i=idx;i<nums.size();++i){
            if(target>=nums[i]){
                if(i!=idx&&i>0&&nums[i-1]==nums[i])continue;//这一行非常重要
                path.push_back(nums[i]);
                dfs(nums,i+1,target-nums[i]);
                path.pop_back();
            }else return;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,target);
        return ans;
    }
};

限制最终方案的元素个数必须为k

216. 组合总和 III

class Solution {
public:
    vector<int>path;
    vector<vector<int>> ans;
    void dfs(int k,int n,int idx){
        if(n==0&&k==0){
            ans.push_back(path);
            return;
        }
        for(int i=idx;i<=9;++i){
            if(n>=i&&k){
                path.push_back(i);
                dfs(k-1,n-i,i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k,n,1);
        return ans;
    }
};

可重复使用具体方案

39. 组合总和

class Solution {
public:
    vector<vector<int>> ans;
    vector<int>path;
    void dfs(vector<int>&nums,int target,int idx){
        if(target==0){
            ans.push_back(path);
            return;
        }
        for(int i=idx;i<nums.size();++i){
            if(target>=nums[i]){
                path.push_back(nums[i]);
                dfs(nums,target-nums[i],i);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0);
        return ans;
    }
};

完全平方数

279. 完全平方数

四平方树定理：(4^a)*(8b+7)

int numSquares(int n) {
    if(int(sqrt(n))*int(sqrt(n))==n)return 1;
    int tmp=n;
    while(tmp%4==0)tmp/=4;
    if((tmp-7)%8==0)return 4;
    for(int i=1;i*i<=n;++i){
        int left=n-i*i;
        if(int(sqrt(left))*int(sqrt(left))==left)return 2;
    }
    return 3;
}

上交题

题目2：输入n(＜1000000)，求所有＜n的k的个数其中，k不能写成k=a1^3+a2^3+...+a8^3的形式的（ai=0,1,2,...）。 输入：小于1亿的正整数n 输出：小于n的无法被3个整数平方和所表示的数字的个数 个人想法：首先，0也可以被3个0的平方和表示，所以也应该被除去。我用3个循环，上限是n^0.5，数出所有能被表示成3个数平方和的数字的个数，然后用n减去。这种方法经过一些剪枝后依然华丽丽的TLE，所以希望有大神提出1s内的方法。