Min Path Num--Typical DP

7月 19 2014

我和刘辉师兄坐在一起，就是你做事情，我突然哈哈大笑，然后我做做事情，你突然哈哈大笑O(∩_∩)O

这道题目属于容易看出的DP，从曹博PPT了看到例子后就反应更快了，不过感觉这个已经是曹博PPT最容易make sense的DP了= =
二维表格记录DP，初始化0 0，以及0 j， i 0, 这样保证后面计算的子问题前面都计算出来了，注意下表不越界，还有就是
leetcode题目都没给数据范围，因此都不敢用全局变量了，正如fawks大神说的，global的比较简单，于是我还是用heap了。。。

附上代码：

int Min(int x, int y)
    {
        if(x<y) return x;
        else return y;
    }
    int minPathSum(vector<vector<int> > &grid) {
        int row=grid.size();
        if(row==0) return 0;
        int col=grid.at(0).size();
        if(col==0) return 0;

        int **dp=new int*[row];
        for(int i=0;i<row;i++)
            dp[i]=new int[col];

        dp[0][0]=grid.at(0).at(0);
        for(int j=1;j<col;j++)
            dp[0][j]=dp[0][j-1]+grid.at(0).at(j);
        for(int i=1;i<row;i++)
            dp[i][0]=dp[i-1][0]+grid.at(i).at(0);

        for(int i=1;i<=row-1;i++)
        {
            for(int j=1;j<=col-1;j++)
            {
                dp[i][j]=Min(dp[i-1][j],dp[i][j-1])+grid.at(i).at(j);
            }
        }
        int max=dp[row-1][col-1];


        for(int i=0;i<row;i++)
            delete[] dp[i];
        delete[] dp;
        return max;
    }

里面需要注意的是没有C++11，所以没有min可能。。。另外我每次都是写完general case再在前面加exception case的，比较舒服，之前一次提交还忘记返回值了= =
自己要逐渐转向不debug，因为后面纸上代码比较多些，直接在leetcode写了，眼睛看了submit

另外今天突然意识到vector可以当数组用的[], 之前一直at写起来麻烦，但是[]不越界检查，后果自负，我还是习惯[]呢，只是list就没有[]了。。
http://zhuyanfeng.com/archives/783

最近发现小米手机Wifi老是断，其他的小米却没有。感觉排除了wifi信号的问题，于是还是之前一直怀疑的系统故意设计这样，节约资源，例如电之类的，不需要的时候自动断掉，但是我需要的时候
也经常断掉啊%>_<%，之前查到好像是德州电器写的wifi驱动里面代码有这么节约资源的设计，好像点到wifi他才连上。。。不太确定，之前想找找帖子解决这个问题的，一直没搞定o(╯□╰)o

一个阿三和我说，她又认识了一个美女，而且是fb主动勾引他的。。。这位可真是把把妹当成一生的主题啊，他还尤其喜欢Chinese girls，尤其是她们的hair style，说一看背后就知道中国女孩，她们都
比印度女孩漂亮，还问我是不是jealous = =

Posted by richard爱闹 - 7月 19 2014
如需转载，请注明：本文来自 Richard

留言