JD1——年終獎

題目描述

小東所在公司要發(fā)年終獎，而小東恰好獲得了最高福利，他要在公司年會上參與一個抽獎游戲，游戲在一個6*6的棋盤上進行，上面放著36個價值不等的禮物，每個小的棋盤上面放置著一個禮物，他需要從左上角開始游戲，每次只能向下或者向右移動一步，到達右下角停止，一路上的格子里的禮物小東都能拿到，請設(shè)計一個算法使小東拿到價值最高的禮物。
給定一個6*6的矩陣board，其中每個元素為對應(yīng)格子的禮物價值,左上角為[0,0],請返回能獲得的最大價值，保證每個禮物價值大于100小于1000。

思路

動態(tài)規(guī)劃

題解

class Bonus {
private:
    int dp[6][6] = {0};
public:
    int getMost(vector<vector<int> > board) {
        dp[0][0] = board[0][0];
        for(int i=1;i<6;i++){
            dp[i][0] = dp[i-1][0] + board[i][0];
            dp[0][i] = dp[0][i-1] + board[0][i];
        }
        for(int i=1;i<6;i++)
            for(int j=1;j<6;j++)
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])+board[i][j];
        return dp[5][5];
    }
};

JD2——拋小球

題目描述

小東和三個朋友一起在樓上拋小球，他們站在樓房的不同層，假設(shè)小東站的樓層距離地面N米，球從他手里自由落下，每次落地后反跳回上次下落高度的一半，并以此類推直到全部落到地面不跳，求4個小球一共經(jīng)過了多少米？(數(shù)字都為整數(shù))
給定四個整數(shù)A,B,C,D，請返回所求結(jié)果。

測試樣例：

100,90,80,70
返回：1020

思路

等比數(shù)列求和（注意彈起落下算兩次路徑）

題解

class Balls {
public:
    int calcDistance(int A, int B, int C, int D) {
        return (A+B+C+D)*3;
    }
};