动态规划

[此贴子已经被作者于2018-11-21 05:15编辑过]

请问怎么记录当前划分数据的权值和保存状态
设sum[n,k]
sum[i,j]= min{sum[i,j],Math.pow(a[i][j])}
感觉不太对

感谢大神耐心的回复！

我想分两段计算 就前面和后面比大小 可是不知道该怎么储存计算值和用哪一部分相比较
如果用三段for循环
minSun(s[n],group[k],n)
s[n]=s1...sn  //初始化输入
group[1]=s1[1] s2[1] ... s[i-1][1]  //n 分组
group[k] =s[i][k] s[i+1][k]...s[n][k]
min=-oo
for i=1 to n
for j=1to k
for t<i-1
    ss[i]=(s[t]+...+s[i])  //第一段和从s[t]加到s[i]
    q=min(q, ss[i]+minSum(ss,group[n-i][j],n-i))   //剩下的长为n-i，最大和sum[n-i] 在N里面从I 到L 位置最小和   
                                                                                          //这里有点懵不知道怎么写
for i=to k
    temp=group[1]^2+...+group[k]^2         // 可是这样感觉就全部遍历一遍了不太好
    best = min(temp,best)
 return best

n9  k4
1 2 3 4 5 6 7 8 9
1 2 3 4 | 5 6 | 7 | 8| 9 |
n5 k3
5 7 11 4 21
5 7 | 11 4 |21

[此贴子已经被作者于2017-4-17 20:30编辑过]

谢大神耐心的回复！

我想分两段计算 就前面和后面比大小 可是不知道该怎么储存计算值和用哪一部分相比较
如果用三段for循环
minSun(s[n],group[k],n)
s[n]=s1...sn  //初始化输入
group[1]=s1[1] s2[1] ... s[i-1][1]  //n 分组
group[k] =s[i][k] s[i+1][k]...s[n][k]
min=-oo
for i=1 to n
for j=1to k
for t<i-1
    ss[i]=(s[t]+...+s[i])  //第一段和从s[t]加到s[i]
    q=min(q, ss[i]+minSum(ss,group[n-i][j],n-i))   //剩下的长为n-i，最大和sum[n-i] 在N里面从I 到L 位置最小和   
                                                                                          //这里有点懵不知道怎么写
for i=to k
    temp=group[1]^2+...+group[k]^2         // 可是这样感觉就全部遍历一遍了不太好
    best = min(temp,best)
 return best

n9  k4
1 2 3 4 5 6 7 8 9
1 2 3 4 | 5 6 | 7 | 8| 9 |
n5 k3
5 7 11 4 21
5 7 | 11 4 |21

谢谢帮主

我找到一个类似栗子
可是看不懂P语言

http://

超级感谢版主大大提供
我在测试的时候发现了一丢丢丢的问题
下面是测试结果
请输入N K的值(中间用空格隔开):
17 10
请输入17个数:
15 3 18 3 21 7 14 2 17 9 20 2 38 4 35 6 23
测试输入数据如下:
15  3   18  3   21  7   14  2   17  9   20  2   38  4   35  6   23  
划分结果如下:
15  |  3   |  18  3   |  21  7   |  14  2   |  17  9   |  20  2   |  38  |  4   35  |  6   23  
最小平方和为6681
//6379

请输入N K的值(中间用空格隔开):
8 4
请输入8个数:
1 1 1 1 1 1 1 1
测试输入数据如下:
1   1   1   1   1   1   1   1   
划分结果如下:
1   |  1   1   |  1   1   |  1   1   1   
最小平方和为18
//应该是16

K SUM

17 5         11605
17 10        6379
17 13        5615
15 3 18 3 21 7 14 2 17 9 20 2 38 4 35 6 23

18 4         41895  //42393
22 3 4 30 39 18 20 29 32 28 25 28 11 17 19 35 21 28

19 6          46561   //47723
19 13       22823
27 47 24 23 32 10 29 3 33 48 48 20 22 11 19 49 21 45 16

24 8          26971  //27591
24 13        17133
24 18        13087
27 31 9 23 37 7 7 18 32 4 8 32 41 8 11 22 22 5 21 32 7 11 33 13

[此贴子已经被作者于2017-4-20 01:05编辑过]

没有关于负数的例子
我刚刚想到一个方法..... 感觉又说不出个什么.... 自底向上的递推公式？
有点类似某个图...?
 求最短路径...?
求1 2 3 4 5 最小值   
高度表示k
n=5 k=3
                                                                                                                 min(5)
     k=3                                             1                                                    12                        123                   1234                 12345
     k=2                                  2,        23,        234                            3,      34,   345             4,    45                 5
     k=1                                 345     45           5                              45,     5                         5

既然每一分段K都存在最小值，那每一段最小值平方加起来应该也是最小值，
但是这样就没有动态规划的意义了......

[此贴子已经被作者于2017-4-21 12:10编辑过]

5 3：5 7 11 4 21   //   810
5 3 : 1 2 3 4 5    //  77
8 4:  1 1 1 1 1 1 1 1    //   16

9 4       1293
9 5        1101
9 7        863
7 11 12 5 3 20 6 5 2

15 10     1177
15 13      957
1 2 3 4 5 6 7 8 9 10 11 12 11 10 8

10 3      15789
10 7       7523
4 38 14 14 15 20 32 13 46 21

10 7    10107
22 27 27 9 39 46 7 13 25 44

12 4        27294
12 7        15630
12 10      11566   
3 44  33 28 21 49 34 6 16 31 40 21

16 7:     9 36|18 29|38 4|24 20|13 17 21|24 15|23 21 14    //15420
16 11:   9 36|18|29|38|4 24|20|13 17|21|24|15 23|21 14   //10404

17 5：  15 3 18 3|21 7 14 2|17 9 20|2 38 4|35 6 23
17 10:   15 3|18 3|21|7 14|2 17|9|20 2|38|4 35|6 23
17 13:   15 3|18 3|21|7|14 2|17|9|20 2|38|4|35|6|23

18 4：  22 3 4 30 39|18 20 29 32|28 25 28 11 17|19 35 21 28     //41895
19 6:     27 47 24|23 32 10 29|3 33 48|48 20 22|11 19 49|21 45 16   //46561
20 15:   21|20|45|30|33|27|12 21|15 21|27|49|45|11 15|28 11|15 14|36   //17458

24 8:    27 31 9|23 37|7 7 18 32|4 8 32|41 8|11 22 22 5|21 32 7|11 33 13   //26971
24 13:  27|31|9 23|37|7 7 18|32 4|8 32|41|8 11 22|22 5 21|32|7 11|33 13   //17133
24 18:   27|31|9 23|37|7 7|18|32|4 8|32|41|8 11|22|22|5 21|32|7 11|33|13   //13087

[此贴子已经被作者于2017-4-27 08:41编辑过]