憶一道百度面試題

部落客參加了百度2015屆校招，最後跪了，其中過程不說，感覺自己确實還是太菜。Anyway，從當下做起，繼續學習。

題意：題目大概的意思是有一個N x N的矩陣方格，在這個矩陣中有M個硬币，每個硬币的位置事先知道，且一個格子最多隻能放一個硬币，現有一個機器人從（0，0）的位置開始走，每次隻能向下或者向右走一格，最終到達（N，N），設計程式計算機器人能拿到的最大的硬筆數。

看到這個題目一看就是一個動态規劃的問題。既然是動态規劃問題，就需要找到狀态和狀态轉換方程。

先做一些設定：

1、coins[N][N]用來表示整個矩陣，用0,1初始化矩陣，若coins[i][j] == 1，表示目前格子有硬币，0則表示沒有硬币；

2、設S[i][j]表示機器人走到第(i, j)這個位置的時候最多能收集的硬币數；

是以很容易想到到達(i, j)位置能收集的最大硬币數等于到達上一個位置所收集的最大的硬币數加上目前位置的硬币數：

S[i][j] = max(S[i - 1][j] ,S[i][j - 1] ) + coins[i][j];
           

下面直接上代碼：
           

#include<iostream>
#include<stdlib.h>

using namespace std;

#define N 4

int MaxCoins(int(*a)[N])
{
	int S[N][N] = {0};

	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			int preMaxCoins = 0;
			int currentCoin = a[i][j];
			//上一個位置有可能是目前位置的正上方的位置
			int preUp = 0;
			//上一個位置有可能是目前位置的正左方的位置
			int preLeft = 0;

			if(i > 0)
				preUp = S[i - 1][j];
			if(j > 0)
				preLeft = S[i][j - 1];

			preMaxCoins = (preUp >= preLeft) ? preUp : preLeft;

			S[i][j] = preMaxCoins + currentCoin;
		}
	}

	return S[N - 1][N -1];
}

int main()
{
	int a[N][N] = { {0,1,1,0},
					{1,0,1,1},
					{0,1,0,1},
					{1,0,1,0}};

	int max = MaxCoins(a);

	cout<<"The max coins is:"<<endl;
	cout<<max<<endl;

	system("pause");

	return 0;
}
           

先到這裡（2014.10.26）