今天看了一道谷歌K數(shù)之和的算法題，忽然想起來之前在力扣上做過2、3、4數(shù)之和的題，覺得很有必要來整理一下。
其實2、3、4數(shù)之和是一類題，用多個指針即可完成；K數(shù)之和是一類題，又是我學的最不好的DP。
假設數(shù)組為A，要找的分別是a、b、c、d，目標為target
2數(shù)之和：固定aPoint。bPoint去找target-A[aPoint];
3數(shù)之和：固定aPoint。bPoint和cPoint組成一個二數(shù)之和的問題，target=target-A[aPoint]；
4數(shù)之和：固定aPoint，bPoint。cPoint，dPoint組成一個二數(shù)之和的問題。
K數(shù)之和：設狀態(tài)為f[i][j][p]，表示前i個數(shù)中找出j個數(shù)且和等于p的方案數(shù)目。
這個問題的關鍵在于到底要不要當前這個數(shù)A[i]。
也就是說，若要滿足當前目標currentTarget，一共有兩條路：
currentTarget的方案數(shù)=不要A[i]的方案數(shù)+要A[i]的方案數(shù)（當然A[i]要比當前目標值小，才能要）

public class Solution {
    public int kSum(int[] A, int k, int target) {
        if(A == null || A.length ==0 || k <= 0)
            return 0;
        //正整數(shù)的總數(shù)從0 - A.length； 可選的個數(shù)從 0 - k; target也是從 0 - target
        int[][][] f = new int[A.length + 1][ k + 1][target + 1];
        //初始值,
        for(int i = 0; i <= A.length; i ++){
            f[i][0][0] = 1;
        }
        //f[i][j][t] = f[i - 1][j][t] + f[i - 1][j - 1][t -A[i]]
        for(int i = 1; i <= A.length; i ++)
            for(int j = 1; j <= k; j ++)
                for(int t = 1; t <= target; t ++){
                    //先更新當前的這個選項，還沒有把第i個數(shù)選擇進來
                    f[i][j][t] = f[i - 1][j][t];
                    //如果想把第i個數(shù)選進來，就要看第i個數(shù)是否大于目前的目標值
                    f[i][j][t] += t - A[i - 1] >=0 ? f[i - 1][j - 1][t -A[i - 1]] : 0;
                }
        return f[A.length][k][target];
    }
}