1029. Two City Scheduling

有 2N 个人，需要被平均分配到 A 和 B 两座城市，每个人分配的花费给出，求最小花费？

题型：DP + 暴力搜索每一个人都可以被分派到 A 或者 B 中，初始花费为0 每次向下传递的时候都可以在前人的每一种情况下选择分配到 A 或者 B DP 二维模型：两种决策，在枚举情况的时候更少的花费会留存传递情况：向下或右下，每次横移一格，重叠部分取最小适用情况：多重有限选择中的暴力记忆化搜索

约束：必须要有N个人选 A，N个人选 B 解决方法：可以规定向右下方传为分配到 B，那么只需要在 [2N][N] 处取结果即可

int twoCitySchedCost(vector<vector<int>>& costs) {
    memset(dp, 0x3F, sizeof dp);
    dp[0][0]=0;

    int n=costs.size();

    for(int i=0;i<n;++i) {
        for(int j=0;j<=i;++j) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]+costs[i][0]);
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+costs[i][1]);
        }
    }
    return dp[n][n>>1];
}

int dp[102][102];

#典型 #搜索 #DP

1025. Divisor Game 1031. Maximum Sum of Two Non-Overlapping Subarrays