790.多米诺和托米诺平铺（DP）

790. 多米诺和托米诺平铺

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

思路：动态规划2110_积木画 蓝桥杯 - 掘金 (juejin.cn)

用dp [ i ] 表示铺平 2* i 的面板的方法的数量

首先考虑只加一字型瓷砖的情况，dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] 。
1、若前 i - 1 行已经铺好，只需在最后一行加一条竖着的一型瓷砖，即dp[ i - 1 ]；
2、若前 i - 2 行已经铺好，只需在最后两行加两条横着的一型瓷砖，即dp[ i - 2 ]；
注意：不能加两条竖着的，因为已经这种情况已经被dp[ i - 1 ]包含了。

然后考虑加L型瓷砖，要铺平 2 * i 的面板，那么L型瓷砖必定需要成对出现，且至少i >= 3，因为两块凑到一起就有2 * 3那么大。
1、若前i - 3行已经铺好，则有2 * dp[ i - 3 ]种方法，因为可以上下翻转
2、若空下2 * 4，2 * 5，2 * 6...的空缺需要L型瓷砖补，则可以将L型瓷砖放在两头，中间填充一型瓷砖，这样就可以补满了，同样上下可以翻转，需要乘以2

所以共有2 * (dp[i-3] + dp[i-4] + dp[i-5] +...+ dp[0])种。

推得：dp[i] = dp[i-1] + dp[i-2] + 2 * (dp[i-3] + dp[i-4] +...+ dp[0])

再进一步：dp[i-1]=dp[i-2]+dp[i-3]+2*(dp[i-4]+...+dp[0])

上式 减 下式得，dp[i] - dp[i-1] = dp[i-1] + dp[i-3]，即 dp[i] = 2 * dp[i-1] + dp[i-3]

class Solution {
public:
    int numTilings(int n) {
        if(n==1)
            return 1;
       int mod=1e9+7;
       vector<int> dp(n+1);//dp [ i ] 表示铺平 2* i 的面板的方法的数量
       dp[0]=1;//dp[0]设为1
       dp[1]=1;
       dp[2]=2;
       for(int i=3;i<=n;i++)
       {
           dp[i]=((dp[i-1]+dp[i-2])%mod+2*dp[0]%mod)%mod;
           dp[0]+=dp[i-2];//用dp[0]记录dp[i-3]+dp[i-4]+...dp[0]的数值
           dp[0]%=mod;
       }
       return dp[n];
    }
};

1664. 生成平衡数组的方案数

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
• 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
• 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：

输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

 思路：DP

        在本题中，如果将下标i的元素删除，那么它之前的元素不会变化，它之后的元素下标全部减1。这意味着，奇变偶，偶变奇，也就是说i之后的奇数下标元素之和将与偶数下标元素之和交换，而i之前的奇数下标元素之和与偶数下标元素之和不变。

        那么，i下标之前的奇数下标和加之后的偶数下标和，得到的就是删除下标i后所有奇数下标的和，同理可以得到偶数下标的和。

        用四个数组分别记录i 之前/之后 的 奇数/偶数 下标元素之和。

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) 
    {
        int odd1 = 0, even1 = 0;//odd1(i前奇数下标元素和),even1(i前偶数下标元素和)
        int odd2 = 0, even2 = 0;//odd2(i后奇数下标元素和),even2(i后偶数下标元素和)
        for (int i = 0; i < nums.size(); ++i) 
        {
            if(i%2!=0) 
                odd2 += nums[i];
            else 
                even2 += nums[i];
        }
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) 
        {
            if(i%2!=0) 
                odd2 -= nums[i];
            else 
                even2 -= nums[i];
            if (odd1 + even2 == odd2 + even1)
                ++res;
            if(i%2!=0) 
                odd1 += nums[i];
            else 
                even1 += nums[i];
        }
        return res;
    }
};