1、矩阵的最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m==0)    return 0;
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;i++)            dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int j=1;j<n;j++)            dp[0][j] = dp[0][j-1] + grid[0][j];

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp = grid[0];
        for (int j = 1; j < n; ++j)            dp[j] += dp[j - 1];

        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j == 0) 		dp[j] = dp[j] + grid[i][j];
                else 				dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
};

2、解码方法（分割整数构成字母字符串）

class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0')   return 0;
        int pre=1,cur=1;
        for(int i=1;i<s.size();i++){
            int temp = cur;
            if(s[i]=='0'){
                if(s[i-1]=='1'||s[i-1]=='2')    cur=pre;
                else return 0;
            }
            else if(s[i-1]=='1' || (s[i-1]=='2' && s[i]>='1' && s[i]<='6')){
                cur+=pre;
            }
            pre = temp;
        }
        return cur;
    }
};