本文共 1476 字，大约阅读时间需要 4 分钟。

1.动态规划题目特点：

有多少种方式走到右下角；有多少种方法选出k个数使得和是sum。（计数）

从左上角走到右下角路径的最大数字和；最长上升子序列长度   （求最大最小值）

取石子游戏，先手是否必胜；能不能选出K个数使得和是sum   （求存在性）

2.解动态规划的步骤

第一:确定状态; 最后一步(最优策略中使用的最后一枚硬币Ak)

                         化成子问题(最少的硬币拼出更小的面值27-Ak)

第二:转移方程    f[x] = min{f[x-2]+1,f[x-5]+1,f[x-7]+1}

第三:初始条件和边界情况     f[0] = 0,如果不能拼出y,f[y]=正无穷.

第四:计算顺序 f[0],f[1],f[2],.......

例题

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 � (1≤�≤100)N (1≤N≤100)，表示三角形的行数。

下面的 �N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

573 88 1 02 7 4 44 5 2 6 5

输出

27

#include 
   
    #include 
    
     //注意：题目中向左下走的次数与向右下走的次数相差不能超过 1，它是最后走的次数之间的差，//并不是每走一步的差。int max(int a,int b)//求最大值{    return a>b?a:b;    }int main(int argc, char *argv[]){  int n,sum=0;  int a[105][105],f[105][105];//a数组用描述题目，f数组用来存储和值  scanf("%d",&n);  for(int i=1;i<=n;i++)    for(int j=1;j<=i;j++)      scanf("%d",&a[i][j]);//输入数据  f[1][1]=a[1][1];//把开头第一个数直接给f数组  for(int i=2;i<=n;i++)//从第二行遍历开始  {      for(int j=1;j<=i;j++)      {          if(j==1) f[i][j]=f[i-1][j]+a[i][j];//每行f数组开头的数就等于a数组本身加上上一行的第一个数          else if(i==j) f[i][j]=f[i-1][j-1]+a[i][j];//末尾的数和上一行相同          else f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];//重点，如果不是本身，则等于数组f的左上和右上的最大值加上数组a本身      }  }  //找规律发现如果n为奇数时，最后必然走到最后行最中间的数，如果为偶数，则取中间两个数的最大值，  //因为向左下走的次数与向右下走的次数相差不能超过 1  if(n%2==1)  printf("%d",f[n][n/2+1]);//奇数情况下  else printf("%d",max(f[n][n/2],f[n][n/2+1]));  return 0;}
    
   

转载地址：https://blog.csdn.net/weixin_73869857/article/details/129481643 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！