LeetCode算法編程（兩題）
1、題目-PlusOne
Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list.
首先解釋下題目，這道題的意思是：
用一個數組來代表一個非負整數，對這個整數進行+1操作，得到的結果也用數組進行表示。這個題目有假設前提：數組裡的數字都是在0-9范圍內的（剛開始弄迷惑了，以為數組裡的數字可以是任意大的值，這樣來解這道題的話，會非常困難）
分析
知道前提後，這個題目就比較簡單了，從數組最後一位開始，每個位需要判斷是否需要進位，如果進位，自已設為0，否則自增即可。直接附源碼：
復制代碼
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int size = digits.size();
if (digits[size - 1] < 9)
{
digits[size - 1] += 1;
return digits;
}
// 是否需要進位
bool carry = true;
for (int i = size - 1; i >= 0; i --)
{
if (!carry)
{
break;
}
if (digits[i] == 9)
{
carry = true;
// 進位後，原位置0
digits[i] = 0;
if (i == 0)
{
// 數組首個數字進位後，需要新插入數字首位
digits.insert(digits.begin(), 1);
}
}
else
{
// 不進位，就退出了
carry = false;
digits[i] += 1;
}
}
return digits;
}
};
復制代碼
2、題目二 - Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
題目解釋：
給出一個 m x n 的矩陣由非負整數組成，找到一條路線（從左上角到右下解）使得路線中經過的數字的累加和最小。
注意：行進的路線只能向下或向右
分析
很明顯這道題，是需要找最優解的題目，而找最優解的問題，最適合的就是動態規劃。
一個動態規劃算法的幾個關鍵點：
1）怎麼描述問題，要把問題描述為交疊的子問題
2）交疊子問題的初始條件（邊界條件）
3）動態規劃在形式上往往表現為填矩陣的形式
4）填矩陣的方式（或者說順序）表明了什麼？--它表明了這個動態規劃從小到大產生的過程，專業點的說就是遞推式的依賴形式決定了填矩陣的順序。
大家可以思考下後，再參考源碼：
復制代碼
/*****************************************************************
采用動態規劃的思想：
1）最優解公式
C(i, j) = Min[ C(i-1, j), C(i, j - 1) ] + Grid[i][j], i > 0, j > 0
2）初始值的邊界情況：
當 i == 0, j == 0時，C(i, j) = Grid[i][j]
當 i == 0, j > 0時，C(i, j) = C(i, j - 1) + Grid[i][j]
當 i > 0, j == 0時，C(i, j) = C(i -1, j) + Grid[i][j]
******************************************************************/
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
int m = grid.size();
int n = grid[0].size();
// 最優解矩陣
vector<vector<int> > c;
vector<int> e;
int d = 0;
for (int i = 0; i < m; i ++)
{
e.clear();
for (int j = 0; j < n; j ++)
{
if (i == 0)
{
d += grid[i][j];
e.push_back(d);
continue;
}
if (j == 0)
{
d = c[i - 1][j] + grid[i][j];
e.push_back(d);
continue;
}
d = d > c[i - 1][j] ? c[i - 1][j] + grid[i][j] : d + grid[i][j];
e.push_back(d);
}
// 一行一行的計算最優解
c.push_back(e);
}
return c[m - 1][n - 1];
}
};
