Dynamic Programming（動態(tài)規(guī)劃）

53. Maximum Subarray

最大和子數(shù)組（元素連續(xù)）
例如題目中給出的例子：

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

代碼：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentSum = 0, maxvalue = INT_MIN;
        for(int i = 0; i < nums.size(); ++i )
        {
            currentSum = max(currentSum + nums[i], nums[i]);
            maxvalue = max(maxvalue,currentSum);
        }
        return maxvalue;
    }
};

思路：
currentSum 是加到第i個元素為止的最大和，maxvalue 是以0,1,2,3……i個元素結(jié)尾的currentSum中最大的currentSum

53.png

動態(tài)規(guī)劃一般解題思路是
（1）將原問題分解為子問題
（2）確定狀態(tài)和初始條件
（3）構(gòu)造狀態(tài)轉(zhuǎn)移方程
一開始接觸動態(tài)規(guī)劃，建議小伙伴們將注意力集中在怎么樣將原問題規(guī)模縮小為子問題，多接觸一些不同類型動歸題目，多動手畫圖表或示意圖，培養(yǎng)分解問題的直覺。

Greedy（貪婪算法）

55. Jump Game

給定一個非負(fù)整數(shù)的數(shù)組，每個數(shù)字表示在當(dāng)前位置的基礎(chǔ)上最多可以走的步數(shù)，求判斷能不能到達最后一個位置。
Input: [2,3,1,1,4]
在第一個元素2處，可以走到第二個元素3，也可以走到第三個元素1

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //reach為以當(dāng)前元素為起點所能達到的最遠元素位置
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            //如果不能到達第i個元素或者reach已經(jīng)達到最后一個元素，則退出
            if (i > reach || reach >= n - 1) break;
            //計算當(dāng)前元素所能到達的最遠元素位置
            reach = max(reach, i + nums[i]);
            cout<<i<<endl;
        }
        cout<<reach<<endl;
        return reach >= n - 1;
    }
};

貪婪算法，顧名思義，就是考慮當(dāng)前每個元素所能達到的最遠距離，滿足條件就可以返回，下面是例子[2,3,1,1,4]的示意圖

55 (1).png

遍歷數(shù)組中的每個元素，查看每個元素所能到達的最遠距離，滿足條件就返回，繼續(xù)看例子[3,2,1,0,4]的示意圖：

55-1.png

怎樣應(yīng)對IT面試與筆試-（一）
怎樣應(yīng)對IT面試與筆試-（二）
怎樣應(yīng)對IT面試與筆試-（三）
怎樣應(yīng)對IT面試與筆試-（四）
怎樣應(yīng)對IT面試與筆試-（五）
怎樣應(yīng)對IT面試與筆試-（五-1）
怎樣應(yīng)對IT面試與筆試-（六）
怎樣應(yīng)對IT面試與筆試-（七）
怎樣應(yīng)對IT面試與筆試-（八）
怎樣應(yīng)對IT面試與筆試-（九）
怎樣應(yīng)對IT面試與筆試-（十）
怎樣應(yīng)對IT面試與筆試-（十一）
怎樣應(yīng)對IT面試與筆試-（十二）
怎樣應(yīng)對IT面試與筆試-（十三）
怎樣應(yīng)對IT面試與筆試-（十四）
怎樣應(yīng)對IT面試與筆試-（十五）
怎樣應(yīng)對IT面試與筆試-（十六）