求助一道题目:
【题目描述】
有一个H行W列的棋盘第i行第j列的棋盘格记为(i,j)。每个格子中都写了两个数,(i,j)中写有整数 $A_ij$ 和Bij。
高桥君首先对每个格子里的两个数染色:一个涂成红色,另一个涂成蓝色。
染色完成后,高桥君从左上角(1,1)出发,每次可以向左或向下走一格,直到到达右下角(H,W)。途中经过的所有格子(包括起点和终点)中红色数字之和记为R,蓝色数字之和记为B。
通过适当的染色以及选取合适的路径,高桥君想要R和B之差的绝对值尽可能的小。问∣R−B∣的最小值是多少?
【输入格式】
输入共2H+1行
第1行,两个正整数H,W
第2到H+1行,每行W个整数,第i+1行第j个数为Aij
第H+2到2H+1行,每行W个整数,第i+H+1行第j个数为Bij
【输出格式】
输出∣R−B∣的最小值
【输入样例#1】
2 2
1 2
3 4
3 4
2 1
【输出样例#1】
0
【输入样例#2】
2 3
1 10 80
80 10 1
1 2 3
4 5 6
【输出样例#2】
2
【样例#1说明】
如下图染色和选择路径,路上红色数总和R=3+3+1=7,蓝色数总和B=1+2+4=7,所以∣R−B∣的最小值是0。
【数据说明】
2≤H,W≤80
0≤Aij,Bij
≤80
求 DP 的状态转移方程