动态规划50题（10/50）

思路：
第三个元素之后，选择与否取决于选择之后和如果不选那种方案值最大

class Solution {
public:
    int rob(vector& nums) {
        if(nums.size() == 1)
        {
            return nums[0];
        }
       int f[101];
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
       for(int i = 2; i < nums.size(); i++)
       {
            f[i] = max(f[i - 2] + nums[i], f[i - 1]);
       }
       return f[nums.size() - 1];
    }
};

思路：

1. 最后一个元素选择与否，取决于第一个元素选择与否
2. 在打家劫舍I 的基础上增加一维

• dp[i][0] 代表第0个元素不选
• dp[i][1] 代表第0个元素选择

3. 最后返回这两种情况的最大值即可

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        int dp[110][2];
        //dp[i][0] 代表第0个元素不选
        //dp[i][1] 代表第0个元素选择
        if(n == 1)
        {
            return nums[0];
        }
        if(n == 2)
        {
            return max(nums[0], nums[1]);
        }
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 2; j++)
            {
               if(i == 1)
               {
                   //如果第0个元素没有选
                   if(j == 0)
                   {
                       //那么最大值就是 0 + nums[1]
                       dp[i][j] = nums[1];
                   }
                   //如果第 0 个元素选了
                   else
                   {
                       //那么第一个元素就不能选
                       //所以到dp[1][1] 的最大值就是nums[0]
                       dp[i][j] = nums[0];  
                   }
               }
               //当遍历到最后一个元素并且在第0个元素选择了的情况下
               else if(i == n - 1 && j == 1)
               {    
                   //到最后一个元素为止，最大的值就是到倒数第二个元素的最大值
                   //因为最后一个元素已经不能选择了           
                    dp[i][j] = dp[i - 1][j];   
               }
               //其他情况按照一般处理即可
               else
               {
                   dp[i][j] = max(dp[i - 1][j], dp[i - 2][j] + nums[i]);
               }
            }
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

思路：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            if(s[i - 1] != '0')
            {
                f[i] += f[i - 1];
            }
            if(i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26))
            {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

思路：

1. 分别统计 0 和 1 的最长字串
2. 看 1 的子串是否大于 0 的字串

class Solution {
public:
    bool checkZeroOnes(string s) {
       int count1 = 0;
       int count0 = 0;
       int diff1 = 0;
       int diff2 = 0;
       for(int i = 0; i < s.size(); i++)
       {
           if(s[i] == '1')
           {
               diff2 = 0;
               diff1++;
               count1 = max(diff1, count1);
           }
           else
           {
               diff1 = 0;
               diff2++;
               count0 = max(diff2, count0);
           }
       }
       return count1 > count0;
    }
};

思路：

1. 先计算前缀和
2. 枚举每个分界的下标 i
3. 看是否符合 当前下标 i 左边的和(presum[i] - nums[i]) 是否等于 i 右边的和(presum[n - i] - presum[i]);
4. 相等则返回 i 否则返回 -1

class Solution {
public:
    int pivotIndex(vector& nums) {
        int n = nums.size();
        int presum[n];
        presum[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            presum[i] = presum[i - 1] + nums[i];
        }
        for(int i = 0; i < n; i++)
        {
            //当前下标的元素不包含，需要减去
            //presum[n - 1] - presum[i]表示后缀和
            if(presum[i] - nums[i] == presum[n - 1] - presum[i])
            {
                return i;
            }
        }
        return -1; 
    }
};

只用找到总和sum的一半的i的坐标返回即可

class Solution {
public:
    int pivotIndex(vector &nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};