State compression DP example (traveling salesman problem and rectangle filling problem)

It's convenient to review later

Given a sheet n A weighted undirected graph of points , Point from 0∼n−1 label , Find the starting point 0 To the end point n−1 The shortest of Hamilton route .

Hamilton The definition of path is from 0 To n−1 Pass through every point exactly once without repetition or leakage .

Input format
Enter the integer in the first line n.

Next n Every line n It's an integer , Among them the first i Xing di j An integer represents a point i To j Distance of （ Write it down as a[i,j]）.

For arbitrary x,y,z, Data assurance a[x,x]=0,a[x,y]=a[y,x] also a[x,y]+a[y,z]≥a[x,z].

Output format
Output an integer , Means shortest Hamilton The length of the path .

Data range
1≤n≤20
0≤a[i,j]≤107
sample input ：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
sample output ：
18

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];

    return 0;
}

// This kind of problem always feels like there is no way to start , All horizontal schemes are all schemes , It feels like searching , Pressure DP I feel I need to rely on experience . The state feels like the volume of the knapsack problem , Is the decision condition ,
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12,M = 1<<N;
int n,m;
long long f[N][M];
bool st[M];
int main(){
    
    while (cin>>n>>m,n||m)
    {
    
        // Preprocessing status   Each column of consecutive null values must be an even number .
        for (int i=0;i<1<<n;i++)
        {
    
            int cnt = 0;
            st[i] = true;
            for (int j=0;j<n;j++)
            {
    
                if (i>>j&1)
                {
    
                    if (cnt&1) st[i] = false;
                    cnt=0;
                }
                else
                cnt++;
            }
            if (cnt&1) st[i] = false;
        }
        
        memset (f,0,sizeof f);
        f[0][0] = 1;
        for  (int i=1;i<=m;i++)
             for (int j=0;j<1<<n;j++)
                for (int k=0;k<1<<n;k++)
                if ((j&k)==0&&st[j|k])    // No overlap ,
                f[i][j] += f[i-1][k];
                
        cout<<f[m][0]<<endl;
    }
    return 0;
}