思维型的dp

题目： 搭积木
参考博客

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=1000000007;
int n,m;
int h[105];    //每列的高度
char mp[105][105];
int f[105][105][2];        //f[pos][hi][fg][r]表示以pos为起点，r为终点，上一列的高度为hi，上升状态为fg时这个二维区间的方法数。
//因为r可以在使用时更新，所以再优化一维，变成f[pos][hi][fg],具体原因看代码

void get_height(){            //得到每一列的高度 
  for(int j=1;j<=m;++j){   
    for(int i=1;i<=n;++i){
      if(mp[i][j]=='X') break;
      h[j]++;
    }
  }
}

int dfs(int pos,int hi,int fg,int r){   //四个参数分别是：当前位置，上一列的高度，当前列的高度是否可以上升，区间右边界
  if(pos>r){
    return f[pos][hi][fg]=1;
  }
  if(f[pos][hi][fg]!=-1) return f[pos][hi][fg];
  ll sum=0;
  for(int i=1;i<=h[pos];++i){
    if(i>hi){
        if(fg) sum=(sum+dfs(pos+1,i,1,r))%mod;
    }
    else{
        if(i==hi) sum=(sum+dfs(pos+1,i,fg,r))%mod;
        else sum=(sum+dfs(pos+1,i,0,r))%mod;
    }
  }
  return f[pos][hi][fg]=sum;  
}

int main(){
  cin >> n >> m;
  for(int i=n;i>=1;--i){
    for(int j=1;j<=m;++j){
      cin >> mp[i][j];
    }
  }
  get_height();
  ll ans=0,l=1,r=1;
  while(l<=m){
    while(l<=m&&mp[1][l]=='X') l++;
    r=l;
    while(r<=m&&mp[1][r]=='.') r++;
    r--;
    for(int j=l;j<=r;++j){
        memset(f,-1,sizeof(f));
      for(int i=j;i>=l;--i){
        ans=(ans+dfs(i,0,1,j))%mod;
      }
    }
    l=r+1;               //让l变成下一个连续区间的起点
  }
  cout << (ans+1)%mod;  //每一列都不放，也是一种方案
  return 0;
}

这题也可用区间dp做