PaintFenceOPT [source code]

public class PaintFenceOPT {
static
/******************************************************************************/
public class Solution {
    public int numWays(int n, int k) {
        int dp[] = {0, k , k*k, 0};
        if (n <= 2) {
            return dp[n];
        }
        for (int i = 2; i < n; i++) {
            dp[3] = (k - 1) * (dp[1] + dp[2]);
            dp[1] = dp[2];
            dp[2] = dp[3];
        }
        return dp[3];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PaintFenceOPT.Solution tester = new PaintFenceOPT.Solution();
        System.out.println(tester.numWays(3, 1));
    }
}

这个是 submission 最优解: 0(7);

这个跟我普通解法的思路其实是差不多的, 不过他这里就是转化成为一维的来考虑了, 当然你也可以理解为就是注意到了之前的表格每个column 其实都是相等的;

值得思考的一点是, 他这里也用了一个手动初始化的技巧; 不过他有一点比我的聪明, 他 table 直接用 literal 来初始化, 这样省的你自己还要 specify table 的维度, which requires you to set a lower bound;

虽然这个算法简练很多, 不过我还是认为首先应该按照我自己的 ver1那样的思路用纯粹的 DP 的思路来做一下. 如果能够把那个思路做出来, 那么其实稍微优化一下到这个版本并不困难, 而且 ver1那个思路其实对于问题的理解帮助要大的多; again, fear the premature optimization.

Problem Description

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Difficulty:Easy
Category:Algorithms
Acceptance:34.23%
Contributor: LeetCode
Companies
google
Related Topics
dynamic programming
Similar Questions
House Robber House Robber II Paint House Paint House II