• 周二. 9月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

526. 优美的排列 力扣(中等) dfs暴搜/ 状压dp是没想到的

admin

11月 28, 2021

526. 优美的排列

假设有从 1 到 N 的 N 个整数,如果从这 N 个数字中成功构造出一个数组,使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个,我们就称这个数组为一个优美的排列。条件:

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N,请问可以构造多少个优美的排列?

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
第 1 个位置(i=1)上的数字是1,1能被 i(i=1)整除
第 2 个位置(i=2)上的数字是2,2能被 i(i=2)整除

第 2 个优美的排列是 [2, 1]:
第 1 个位置(i=1)上的数字是2,2能被 i(i=1)整除
第 2 个位置(i=2)上的数字是1,i(i=2)能被 1 整除

题解:

法一:dfs搜索可以想到

法二:https://leetcode-cn.com/problems/beautiful-arrangement/solution/yi-ti-wu-jie-dfs-bao-sou-ji-yi-hua-dp-zh-qblw/

dfs+bool vis[]—–>dfs+状态压缩——发现有些状态重复—->记忆化搜索——-> 状压dp

dfs爆搜代码:自己做的方法

class Solution {
public:
    int res=0;
    bool vis[20];
    void dfs(int k,int n)
    {
        if(k>n) {res++; return;}
        for(int i=1;i<=n;i++)
        if(i%k==0 || k%i==0)   // 第k位,放数字i可不可以
        {
            if(!vis[i])
            {
                vis[i]=1;
                dfs(k+1,n);
                vis[i]=0;
            }       
        }
        return;
    }

    int countArrangement(int n) {
    // 暴力做法dfs
      memset(vis,0,sizeof(vis));  
      dfs(1,n);
      return res;
    }
};

记忆化搜索,不好写:

class Solution {
public:
    
    int f[20][(1<<15)+5];
    int dfs(int k,int vis,int n)  // 此时,第k位还没放,访问过的数字用vis二进制表示
    {
       if(k>n) return 1;      // n位数字已经放完了
       if(f[k][vis]) return f[k][vis];   // 说明这种状态已经计算过了;记忆化搜索核心
      
      int ans=0;
       for(int i=1;i<=n;i++)     // 数字i是不是可以放
         if((i%k==0 || k%i==0) && (vis&(1<<(i-1)))==0)
              ans+=dfs(k+1,vis|(1<<(i-1)),n);
        return f[k][vis]=ans;
    }

    int countArrangement(int n) {
    // 暴力做法dfs,记忆化搜索
    memset(f,0,sizeof(f));
    return dfs(1,0,n);

    }
};

View Code

进而,改写成,状压dp,不会

class Solution {
public:
    
    int f[20][(1<<15)+5];
    int countone(int x)
    {
        int sum=0;
        while(x>0){ if(x%2==1) sum++; x/=2;}
        return sum;
    }
    int countArrangement(int n) {
    // 暴力做法dfs,记忆化搜索,状压dp
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int vis=0;vis<(1<<n);vis++)  
        if(countone(vis)==i) //  数字放到第i位,所以状态中应该恰有i个1
        {
            for(int k=1;k<=n;k++)
            {
                if( (vis& (1<<(k-1)) )!=0  && (k%i==0 || i%k==0) )  // 表示第i个位置放k,满足条件
                 f[i][vis]+=f[i-1][ vis & (~(1<<(k-1))) ];
            }
        }
    }
    return f[n][(1<<n)-1];
    }
};

View Code

发表回复

您的电子邮箱地址不会被公开。