帮朋友发google onsite面经

可以根据杨氏矩阵的性质进行剪枝

我觉得我的这个dp应该是work了，结果有701149020种（7亿种，确实很多）。不过是秒出的结果。所以应该是work了
code如下：

int count(int n) {
    map<vector<int>, int> countMap;
    countMap[vector<int>(n, 0)] = 1;
    for (int i = 1; i <= n * n; i++) {
        map<vector<int>, int> newCountMap;
        for (auto cur : countMap) {
            vector<int> curVec = cur.first;
            int curCount = cur.second;
            for (int j = 0; j < n; j++) {
                if ((j == 0 || curVec[j] < curVec[j - 1]) && curVec[j] < n) {
                    curVec[j]++;
                    newCountMap[curVec] += curCount;
                    curVec[j]--;
                }
            }
        }
        countMap = newCountMap;
    }
    return countMap.begin()->second;
}

解释一下：这里是逐个填入1到25的，dp是用在了 “只考虑count，不记录结果” 这一点上面。其中countMap是一个把vector映到int的map，vector就表示当前的选取方法，而int是选取方法对应的count数，
比如vector是 [4,3,2,1,1] 就表示第一行填了前4个，第二行填了前三个这样这样。（因为4+3+2+1+1=11，所以当前一定是在处理i=11这个数）每次一个大循环的loop结束后，newCount里面就存了填入第i个数后，所有的填法以及每个填法对应的count。所有可能的状态数大概是 5! 种（也就是非严格单减序列的个数，比 5!稍多，不过差不太多，）每个状态数会用常数时间（严格来说是 O(5)）处理，所以整体的时间比最终的结果数小很多。

另外，如上code使用了map，略微拖慢了运行速度（虽然算5x5的基本看不出来什么区别）。
可以换成一个5x5x5x5x5的数组+queue做bfs，来处理是否访问过的问题。这样会把复杂度扔掉一个log factor

我还做了些其他测试，事实发现这个东西随n增大（这里n=5），那个count数涨的非常快。
n=1: 1
n=2: 2
n=3: 42
n=4: 24024
n=5: 701149020
n=6: 1671643033734960 (已经超出 int的范围了，是用long 算的）

我的code可以跑n=10，大概要3秒左右。复杂度基本是 n! 量级，当然n=10的结果肯定就是错的了，这个count随n增大会迅速变成天文数字。

163 发表于 2016-1-10 12:51
我觉得我的这个dp应该是work了，结果有701149020种（7亿种，确实很多）。不过是秒出的结果。所以应该是work ...

好厉害！！！DFS+backtracing用了剪枝40+秒，是应该用DP做更好，厉害！

Uique Path的follow up 楼主是怎么解决的啊?

想知道unique path follow -up 怎么解的?

163 发表于 2016-1-11 01:51
我觉得我的这个dp应该是work了，结果有701149020种（7亿种，确实很多）。不过是秒出的结果。所以应该是work ...

不太懂c++ code，这个countMap对应的是java中的hashmap? 那vector<int>是array, 如果这样的话这key有点奇怪啊

两个人一起走那个能先用dp算一个人的 同时刷新矩阵 再用dp算第二个人的 求和。不知道对不对

kinggarden2001 发表于 2016-2-4 12:27
两个人一起走那个能先用dp算一个人的 同时刷新矩阵 再用dp算第二个人的 求和。不知道对不对

应该走一遍就可以。。。每次取最好的两个

同想问路径和的follow应该怎么考虑