PaintFence [source code]

public class PaintFence {
static
/******************************************************************************/
public class Solution {
    public int numWays(int n, int k) {
        int[][] memo = new int[Math.max(n + 1, 3)][Math.max(k + 1, 1)];
        for (int i = 0; i < k; i++) {
            memo[0][i] = 0;
            memo[1][i] = 1;
            memo[2][i] = k;
        }
        memo[0][k] = 0;
        memo[1][k] = k;
        memo[2][k] = k * k;
        for (int i = 3; i <= n; i++) {
            int sum = 0;
            for (int j = 0; j < k; j++) {
                memo[i][j] = memo[i - 1][k] - memo[i - 1][j] + memo[i - 2][k] - memo[i - 2][j];
                sum += memo[i][j];
            }
            memo[i][k] = sum;
        }
        return memo[n][k];
    }
}
/******************************************************************************/

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

首先, 一个思路上的选择, 虽然以前我们不这么说, 但是 DP 问题, 其实关键点也是找一个有DP property的recursive value, 这个 value 就是 table 的 entry; 在找这个 value 的过程中, 一个常见的策略就是增加维度, 这个有点类似于之前 tree 问题的时候, 如果直接只说 value 是什么, 可能没有DP property, 但是如果加一个要求让 value 跟 root 挂钩, 就有可能找到 DP Property; 这里也是一样, 第二维是 i 的颜色, 这个就是decision for post i, 其实就是一个让这个 value 跟 i(root) 挂钩的做法;

感觉 DP 问题的核心还是, 首先找到一个具有 DP Property 的 value 来作为 entry; 然后利用 tree 问题里面的 recursion 的观点, 站在[i][j]这个点, which children you want to pick so that you can calculate [i][j] ? 跟tree 问题比较大的不同要么就是 tree 问题里面的 children 都是固定的(左右两个), 但是在 DP 问题上面, 很多时候难点就是你选择 which children, 以及怎么组合/处理他们;

Verbal Logic

找到这个 recursion 处理 formula 的核心, 就是当你确定你已经找到了 DP Property 的时候, 你要尽量 verbally, 表达出这么一个逻辑上的 recursion 关系. 这个过程可能非常的抽象和高层面, 不过如果你的 DP Property 找的是对的, 那么这个逻辑是找得到的;

另外, 这个题目也充分展示了举例总结的重要性, 我在设计这个算法的过程中就是一直假设 k 是3, 然后自己一个一个的推; 别总是想着从最抽象的例子里面来直接就能提炼规律;

刚开始我的逻辑不是上面的代码这样, 我认为[i][j]应该是[i-1][j]sum on j, 全部加起来, 然后减掉[i-2][j]就行了;
0 1 3 8 21 55
0 1 3 8 21 55
0 1 3 8 21 55
这个是得到的一个 table. 这个是不对的;

• 我的逻辑是, 比如在计算(注意, 这个表格是转置过的, 为了看起来方便)[4][0]的时候, 我用: [3][0] + [3][1] + [3][2] - [2][0] = 8 + 8 + 8 - 3;
• 但是正确的逻辑应该是[3][1] + [3][2] + [2][1] + [2][2] = 8 + 8 + 3 + 3;

我的逻辑的错误之处通过Verbal Logic其实是不难发现的:
我的逻辑的本意是: # of selecting 0 @ [4], is first sum # of selecting any @ [3], then minus # of selecting 0 @ [2].
这样一自己说给自己听, 你就知道哪里有问题了, 你最后减掉的这个, 不应该是# of selecting 0 @ [2], 而应该是# of selecting 0 @ [2] and also selecting 0 @ [3]. 这个类似 intersection/land 的值如果计算, 其实也只能用 8 - 3 - 3 (select 0 @ [3] but NOT selecting 0 @ [2]).
仔细想了一下, 这个 intersection的值好像除了 complement 的思路, 还真的是没有办法计算了?

Is Row0 Necessary?

row0有时候不好处理; 不行就自己手动把 row1和 row2先填起来, 也就是等于直接无视 row0了; 不过这种提前初始化, 有时候要注意对于表格的维数有一个下限;

Count DP

在这种 value 是#的 DP 问题当中, 在思考逻辑的时候可能有一些困难, 因为如果只是一个普通的, 比如 cost, 你直接用一些 min max 之类的东西就可以计算出来. 但是如果是 count 类的, 你就要用大略的枚举(当然, 是带有分类的枚举)来考虑这个count 里面的那些具体的 record 可以符合你的要求. 这个可能有点复杂, 不过要注意这么一个方法论上的细分;

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