动态规划——坐标型

絮絮叨叨：大家好哦，接下来我将要和大家一起学习动态规划，对于这块我现如今还是一名小笨鸟，我分享了一些我在学习中的方法，若有不对或者你有更好的办法，谢谢你提出来，我们一起进步。

动态规划一般分为三大部分：

• 坐标型动态规划
• 序列型动态规划
• 划分型动态规划

今天主要来学习坐标型动态规划

以下是我的做题步骤：

1. 确定状态 确定子问题，突破口是研究最后一步的解法
2. 转移为方程 写出该问题的方程
3. 初始和边界情况 做到无重复、不遗漏

我将从下面几道题来演示这几个步骤

一个机器人位于一个 m x n 网格的左上角 
（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

来源：力扣（LeetCode）

一. 确定状态 · 研究最后一步：机器人需要走到（m-1，n-1)处，那么它只有两种走法——从上方（m-2，n-1)走下来，从左方（m-1,n-2）处向右走来。假设有num种方法走到（m-2，n-1)处，有sum种方法走到（m-1，n-2)处，则机器人就有num+sum种方法走到（m-1，n-1)处 · 确定子问题： 这里用数组 store[m][n] 来存储机器人走到网格（i，j）位置的不同路径。位置 (m,n) 表示机器人需要走到的位置。 (m-1,n-1)——>store[m-2][n-1]+store[m-1][n-2] (m-2,n-1)——>store[m-3][n-1]+store[m-2][n-2] ... ( i , j )——>store[i-1][ j ]+store[ i ][j-1] ... ( 1 , 1 )——>store[ 0 ][ 1 ]+store[ 1 ][ 0 ]

二.转移为方程

 store[ i ][ j ]=store[i-1][ j ]+store[ i ][j-1];

三. 初始和边界情况 ·初始： 机器人走到A[0][0]的路径有1种

 store[0][0]=1;

·边界： 当机器人位于 i==0 处，机器人只能从左边向右走，只有一种路径。 当机器人位于 j==0 处，机器人只能从上边向下走，只有一种路径。

 if(i==0||j==0) store[i][j]=1;

代码 机器人需要走到 (m-1,n-1)处的不同路径的答案为store[m-1][n-1]

int uniquePaths(int m, int n){
    int store[m][n],i,j;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++){
            if(i==0||j==0) store[i][j]=1;
            else{
                store[i][j]=store[i-1][j]+store[i][j-1];
            }
        }
        return store[m-1][n-1];
}

絮絮叨叨：在解决动态规划问题时，需要新开一个数组来存储上一次的记录