我正在尝试解决一个动态编程问题,部分问题涉及找到一组“p”数字的排列数,这些数字总和为一个数字“n”。p 个数集合中的每个数应介于 0 到 n 之间。
例如,如果 n = 4 和 p = 3,我有以下 12 个排列
{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}
我从这种 DP 方法开始。
n(i,j) represents number of ways of representing n using i,j in p positions
我的基本情况是
n(i,0) = n(0,i) = p
(例如,p=3 处的 n(4,0) 为 3,即 {4,0,0},{0,4,0},0,0,4}
递归案例
n(i,j) = n(i,j-1)*n(i-1,j)
(例如:n(1,2) = n(1,1) * n(0,2) 递归到 n(1,0) * n(0,1) * 2)
我不确定我是否朝着正确的方向前进,因为上述方法并没有让我得到正确的答案。请指导我正确的方向。