动态规划-----方格取数洛谷c语言

动态规划-----方格取数洛谷c语言

这是一个比较简单的动态规划，算是入门，其实我也不太懂这个，就是刷到这个题了解了一下，以后再有了解的话，会给大家继续分享的哈哈哈。

文章目录

• 洛谷方格取数
• 题目描述
• 思路
• • 代码
• 总结

---

洛谷方格取数

---

提示：以下是本篇文章正文内容，下面案例可供参考

题目描述

设有 N × N N times NN×N 的方格图 ( N ≤ 9 ) (N le 9)(N≤9) ，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0 00 。如下图所示：

思路

代码

代码如下（示例）：

#include
int max(int a, int b, int c, int d)
{
 if (a < b) a = b;
 if (a < c) a = c;
 if (a < d) a = d;
 return a;
}
int main()
{
 int shu[10][10] = { 0 }, an[10][10][10][10] = { 0 }, term = 0;
 int n = 0, a = 0, b = 0, c = 0;
 scanf("%d", &n); getchar();
 scanf("%d %d %d", &a, &b, &c);
 for (; a != 0 || b != 0 || c != 0;)
 {
  shu[a][b] = c; scanf("%d %d %d", &a, &b, &c); getchar();
 }
 for (int i = 1; i <= n; i++) 
  for (int j = 1; j <= n; j++) 
   for (int b = 1; b <= n; b++) 
    for (int k = 1; k <= n; k++)
    {
     an[i][j][b][k] = max(an[i - 1][j][b - 1][k], an[i - 1][j][b][k - 1], an[i][j - 1][b - 1][k], an[i][j - 1][b][k - 1])+ (shu[i][j] + shu[b][k]) / ((i == b && j == k) ? 2 : 1);//状态方程
    }
 printf("%d", an[n][n][n][n]);
 return 0;
}

总结

这道题理解的还不够透彻，下去还得多加理解，通过这个题还可以学习一下动态规划，现在开始会学习算法的，如果有大佬对这个题有更好理解的可以私信我谢谢谢谢谢谢！