显然调整到相邻高度最优

考虑dp，显然修改$a_i$时可直接转移

考虑滚动数组以降低空间复杂度，故设如下状态

设$f_{i,j,0}$表示已经建了j座房子，且最后一座在第$i-1$个位置之前的最小次数

$f_{i,j,1}$表示已经建了j座房子，且最后一座在第i个位置的最小次数

$f_{i,j,2}$表示已经建了j座房子，且最后一座在第$i-1$个位置的最小次数

则可得转移 $$ f_{i,j,0}=min(f_{i-1,j,0},f_{i - 1,j,2}) $$

$$ f_{i,j,1}=min(f_{i,j-1,0}+max(0,a_{i-1}-a_i+1),f_{i,j-1,2}+max(0,min(a_{i-1},a_{i-2}-a_i+1))) $$

$$ f_{i,j,2}=f_{i-1,j,1}+max(0,a_i-a_{i-1}+1) $$

注：$max(0,x)$表示如果差大于0则调整，否则无需调整

滚动数组转移即可，注意滚动数组后转移需注意实现细节