leetcode 276 排列组合

这个题一上来我也是蒙的，痛恨自己高中排列组合没好好学？哈哈，本仙女高中数学可是好得很，应该是很少见这种情况，下次要记住哟。严肃脸 立下一个flag:

• 解题思路：

  
  WeChat Image_20190106150011.jpg
  

  因为可以两个连续的fence,但是三个就不可以，所以先分析两个涂相同+不同的情况，然后将所有结果作为下一次的k,然后进行计算。有人能证明这一定是对的吗？

• code:

int numWays(int n, int k) {
        if(n==0)
            return 0;
        int diff=k;
        int same=0;
        for(int i=2;i<=n;i++){
            int temp=diff;
            diff=(same+diff)*(k-1);
            same=temp;
        }
        return same+diff;
    }