8.13 dp: triangle & maximumS

to do

13.1] Triangle

一开始理解错了，adjacent是说下一行可以保持index或是index+1

- naive method

n*n space and build from top of triangle to bottom

    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()) return 0;
        int lastLineLen = triangle[triangle.size()-1].size();

        vector<vector<int>> minSum (triangle.size(), vector<int>(lastLineLen, INT_MAX) );
        minSum[0][0] = triangle[0][0];
        for (int row=1; row<triangle.size(); ++row) {
            for (int index=0; index<triangle[row].size(); ++index) {
                for (int lastRowIndex = index-1; lastRowIndex <index+1; ++lastRowIndex) {
                    if (lastRowIndex<0 || lastRowIndex>=triangle[row-1].size()) continue;
                    minSum[row][index] = min(minSum[row][index], minSum[row-1][lastRowIndex]+triangle[row][index]);
                }
                // cout<<"minSum["<<row<<"]["<<index<<"]="<<minSum[row][index]<<endl;
            }
        }
        return *min_element(minSum[minSum.size()-1].begin(), minSum[minSum.size()-1].end());
    }

- Better version.

Use O(n) space and build from bottom to top in avoidance of index out of bound

    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()) return 0;
        vector<int> lowerRow = triangle[triangle.size()-1];
        for (int row=triangle.size()-2; row>=0; --row) {
            vector<int> higherRow(triangle[row].size(), -1);
            for (int i=0; i<higherRow.size(); ++i) {
                higherRow[i] = triangle[row][i] + min(lowerRow[i], lowerRow[i+1]);
            }
            lowerRow = higherRow;
        }
        return lowerRow[0];
    }

13.2] maximum-subarray

- If exists no negative numbers, simply keep adding to find the maximum.

    int maxSubArray(vector<int>& nums) {
        int maxSoFar = 0, maxEndingHere = 0; 
        for (int i=0; i<nums.size(); ++i) {
            maxEndingHere += nums[0];
            maxSoFar = maxEndingHere<0? 0 : max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

- add the negative cases. It means we'll make comprimise when considering if we should add the last new number.

• Assume we've solved subproblems where input string length <=n and stored answers in array maxSumArr: maxSumArr[i] gives the maximum sum of subarrary ending with s[i].
• Now consider incremental step where string s of length n+1
  • case 1: add s[n+1] to maxSumArr[n]. Only meaningful if maxSumArry[n]>=0
  • case 2: Else if maxSumArry[n]<0, start newSubArray with s[n+1]
  • => maxSumArry[n+1] = max(maxSumArry[n]+s[n+1], s[n+1]);
  • base case: maxSumArry[0] = s[0]
  • what to return?

    int maxSubArray(vector<int>& nums) {
        vector<int> maxSumArr = {nums[0]};
        for (int i=1; i<nums.size(); ++i) {
            maxSumArr.push_back( max(maxSumArr[i-1]+nums[i], nums[i]) );
        }
        return *max_element(maxSumArr.begin(), maxSumArr.end());
    }

mark redo w/ divide and conquer

优化的暴破法只要O（n）是的只要O（n）你没有看错走过路过不要错过

13.3] Palindrome Partitioning II

redo !!!!

dp for isPalin table,
dp for partitioning string

    bool isPalindrome(string s) {
        for (int l=0, r=s.size()-1; l<r; ++l, --r) {
            if (s[l] != s[r]) return false;
        }
        return true;
    }
    
    int minCut(string s) {
        if (s.size()<2) return 0;
        vector<vector<bool>> isPalin(s.size(), vector<bool>(s.size(), true));
        // build isPalin lookup table
        for (int i=s.size()-1; i>=0; --i) {
            for (int j=i; j<s.size(); ++j) 
                isPalin[i][j] = i==j? true : isPalin[i+1][j-1] && s[i]==s[j]; // init to true took care of basecases
        }
        // for (auto& v: isPalin) {
        //     for (int i=0; i<v.size(); ++i) cout<<" "<<i<<":"<<v[i];
        //     cout<<endl;
        // }
        // build dp array
        vector<int> minCut(s.size(), INT_MAX);
        for (int i=0; i<s.size(); ++i) {
            // find a pivot to cut into a palindrome and a solved sub-problem
            for (int k=0; k<=i; ++k) {
                if (isPalin[k][i]) {
                    if (k==0) {
                        minCut[i] = 0;
                        break;
                    }
                    minCut[i] = min(minCut[i],  minCut[k-1] + 1);
                    // cout<<"curr"<<curr<<"=minCut["<<k<<"-1] = "<<minCut[k-1]<<" minCut["<<i<<"]"<<minCut[i]<<endl;
                }
            }
        }
        return minCut[s.size()-1];
    }