用动态规划求解均分纸牌

Question

均分纸牌：
从键盘输入n，表示有n堆卡片，并输入每堆卡片的张数（总的张数不一定是n的倍数）。现在任意两堆 卡片之间，移动任意张卡片，最终目标是让最多一堆的卡片张数与最少一堆的卡片张数的差小于等于1。规定将第i堆的一张卡片移动到第j堆，或者将第j堆的一张卡片移动到第i堆代价均为i-j的绝对值。
例如，当n=5，每堆张数分别是5,9,2,12,9时，最小移动代价是8。
1 #include
2 #include<windows.h>
3 using namespace std;
4 const int M=10;
5 long dp[M][M],card[M],s[M];
6 int main(){
7 int n,i,j;
8 cin>>n;
9 for (i=1;i<=n;i++){
10 cin>>card[i];
11 s[i]=s[i-1]+card[i];
12 }
13 int r=s[n]%n,q=s[n]/n;
14 for(i=1;i<=n;++i){
15 for(j=0;j<=r;++j){
16 int c=abs(s[i]-q*i-j);
17 dp[i][j]=dp[i-1][j]+c;
18 if(j)
19 dp[i][j]=min(dp[i-1][j-1]+c,dp[i][j]);
20 }
21 }
22 cout<<dp[n][r]<<endl;
23 return 0;
24 }
请问程序第17，19行的含义，怎样理解第19行的状态转移方程的含义

Answer 1

使用动态规划计算最小操作次数达到目标状态。

以上回复有部分引自免费微信小程序：皆我百晓生。 如问题尚未解决，还请稍待，如有疑问请回复进一步沟通。