【动态规划】【前缀和与dp】2811. 判断是否能拆分数组

class Solution {
private: 
    int mx = 0;
public:
    vector<vector<bool>>dp;
    vector<vector<int>>vis;
    bool dfs(vector<int>& nums, int i, int j) {
        if (i == j || (j == i + 1)) {
          dp[i][j] = true;
            return true;
        }
        // cout << "i,j " << i << " " << j << "：" << endl;
        if (vis[i][j] == 1) {
          return dp[i][j];
        }
        vis[i][j] = 1;
        for (int k = j -1; k >= i; k--) {
            int sumLL = prefix[k + 1] -prefix[i];
            int sumRR = prefix[j + 1] - prefix[k + 1];
            if ((sumLL < mx  && k != i) || (sumRR < mx && ((k + 1) != j))) {
              continue;
            }
            bool res = dfs(nums, i, k) & dfs(nums, k + 1, j);
            if (res == true) {
              dp[i][j] = true;
              return true;
            }
        }
        dp[i][j] = false;
        return false;
    }
    vector<int>prefix;
    void sumPre(vector<int>& nums) {
        for(int i = 1; i <= nums.size(); i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }
    bool canSplitArray(vector<int>& nums, int m) {
      dp.resize(nums.size(), vector<bool>(nums.size(), false));
      vis.resize(nums.size(), vector<int>(nums.size(), 0));
      if (nums.size() == 1) return true;
        mx = m;
        prefix.resize(nums.size() + 1, 0);
        sumPre(nums);
        bool ans = dfs(nums, 0, nums.size() -1);
        return ans;
    }
};