动态规划学习日记（二）weixin43869733的博客-

（这次是两个不同类型的简单例题）

例2、有m行n列网格，从左上角走到右下角，求有多少种方式（方式数问题）

分析：

一、确定状态：

终点：最右下角的坐标为（m – 1，n – 1），前一步坐标必为（m – 2，n – 1）或（m – 1， n – 2）；

子问题：利用加法原理，设有x种方式走到（m – 2，n – 1），有y种方式走到（m – 1， n – 2），则有

​ x + y种方式走到终点。设f[i] [j]为方式数。

二、确定转移方程：

f[i] [j] = f[i – 1] [j] + f[i] [j – 1]

三、确定初始条件和边界情况：

初始条件：f[0] [0] = 1；

边界情况：i == 0 || j == 0， f[i] [j] = 1;

四、确定计算顺序：

逐行计算，因为已知边界行和列的初值

代码：

#include <iostream> #include <cstring> using namespace std; int mp[100][100]; void Init(int m, int n){  int i, j;  for(i = 0; i < m; i++)  {    mp[i][0] = 1;  }  for(i = 0; i < n; i++)  {    mp[0][i] = 1;  } } void Fill(int m, int n){  int i, j;  for(i = 1; i < m; i++)  {    for(j = 1; j < n; j++)    mp[i][j] = mp[i-1][j] + mp[i][j-1];  }  } int main(int argc, char** argv) {  memset(mp, 0, sizeof(m));     int m, n;  cin>>m>>n;  Init(m, n);   Fill(m, n);  cout<<mp[m-1][n-1]<<endl;  return 0; } 

例3、有n块石头，一只青蛙从位置0跳到n-1，青蛙站在i块石头上，最多可以向右跳ai，问青蛙是否能跳到石头n-1（存在性问题）

一、确定状态：

终点：位置n-1，前一步位置n – 1，需满足：1、i < n – 1; 2、青蛙可以从0跳到i；3、n – 1 – i <= ai；

子问题：设f[j]表示青蛙能否跳到石头j

二、确定转移方程：

f[j] = OR(0 <= i < j)(f[i] AND i + a[i] >= j)(0 <= i < j：枚举上一个石头i，f[i]：青蛙能否跳到i， i + a[i] >= j：终点距离限制)

三、确定初始条件和边界情况：

初始条件：f[0] = True，无边界

四、确定计算顺序：

由f[j] = OR(0 <= i < j)(f[i] AND i + a[i] >= j）说明顺序为从小到大

代码：

#include <iostream> #include <cstring> using namespace std; int a[100]; int f[100]; void Init(){  memset(a, 0 ,sizeof(a));  memset(f, 0 ,sizeof(f));  f[0] = 1;   } void F(int n){  int i, j, flag;  for (i = 1; i < n;i++)  {   flag = 0;   for(j = 0; j <= i - 1;j++)   {    if(f[j] == 0 || j + a[j] < i)    {     continue;     }    else    {     flag = 1;     break;    }    }   if(flag)   {    f[i] = 1;   }   else   {    f[i] = 0;   }   } } int main(int argc, char** argv) {  Init();  int n;  cin>>n;  int i;  for(i = 0; i < n; i++)  {   cin>>a[i];  }  F(n);  cout<<f[n - 1]<<endl;  return 0; } 

**总结：**转移方程的一般形式：最值问题：min 或者 max{…}; 计数问题：f[…] + f[…]; 存在性问题：
OR… AND…