partition_souvenirs.java

    public static int partitionKDim(int[] A, int k, int target) {

      int[][][] mem = new int[k + 1][A.length + 1][target + 1];

      for (int t = 0; t < k + 1; t++) {
        for (int i = 0; i < A.length + 1; i++) {
          mem[t][i][0] = 1;
        }
      }

      for (int t = 1; t < k + 1; t++) {
        for (int i = 1; i < A.length + 1; i++) {
          for (int j = 1; j < target + 1; j++) {
            mem[t][i][j] = mem[t][i - 1][j];
            int p = j - A[i - 1];
            if (p >= 0) {
              mem[t][i][j] = mem[t][i][j] + mem[t - 1][i - 1][p];
            }
          }
        }
      }

      for (int t = 0; t < k + 1; t++) {
        printSquare(mem[t]);
      }

      return mem[k][A.length][target];
    }