lintcode-k数和

• 动态规划（确定0-1背包、完全背包、多重背包）
  • 0-1背包：每个元素要么出现，要么不出现，逆序遍历，数组定义为：前i个元素在不超过体积V的前提下，所能达到的最大值，初始值均为0
  • 完全背包：每个元素可以出现无数次，顺序遍历，数组定义为：前i个元素体积刚好为V的情况下，所能达到的最大价值，初始值为不存在(无穷),dp[0] = 0
  • 多重背包：通过拆分，转换为0-1背包
• 注意点
  • 所有数组元素都要有初始值，全为0的情况特殊考虑
  • 多维数组优化

//0-1背包
class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
         if(A.size() < k || k == 0)
            return 0;

        int dp[k+1][target+1];
        
        for(int i = 0; i <= k; ++i) {
            for(int j = 0; j <= target; ++j) {
                dp[i][j] = 0;
            }
        }
        
        dp[0][0] = 1;
        
        for(int i = 0; i < A.size(); ++i) {
            for(int j = k; j >= 1; --j) {
                for(int s = target; s >= A[i]; --s) {
                    dp[j][s] = dp[j-1][s-A[i]] + dp[j][s];
                }
            }
        }
        
        return dp[k][target];
    }
};