前言

在leetcode中有一些题目需要利用动态转移的思路去解决问题，这种解决方法能够与最终结果去相匹配，减少了求解过程中的麻烦。

例题1

假如有这么一个数组，要求它的最大子数组和，那么可以肯定每个元素前后都是有联系的。

所以我们有这样一个思路：

数组从头开始移动，用一个变量pre来记录当前数组之和，当走到某个元素时，需要判断pre+当前元素与当前元素的大小，大者返回到pre。如下图，

第一行为数组nums，第二行为pre记录当前数组和大小，这就是动态规划转移的思路，将原数组根据要求转换成新的结果。根据题目要求还需要求最大的数组和，所以还需要一个变量max来记录最大的数组和。

代码如下：

int maxSubArray(int* nums, int numsSize){
    int i=0;
    int pre=0,Max=nums[0];
    //利用动态规划转移的思路
    for(i=0;i<numsSize;i++)
    {
        pre=fmax(pre+nums[i],nums[i]);
        //将指针所指当前数加上pre与之前的pre数相比，返回较大者
        Max=fmax(pre,Max);
        //将之前的最大数与当前pre相比，返回最大者
    }
return Max;
}

当然，由于我是用整型变量来记录，pre与max会随着循环走动而变动，所以上述思路只是画图讲解，不存在另一个数组。下面就讲一条用数组来记录的。

例题2

例如

用一个sum数组来记录动态转移之后的数组

代码如下：

int maxProfit(int* prices, int pricesSize){
//利用动态规划转移的方法
int i=0,max=0;
int min=prices[i];
int* sum=(int*)malloc(sizeof(int)*pricesSize);
sum[0]=0;
for(i=1;i<pricesSize;i++)
{
   min=fmin(min,prices[i]);
   //找出当前最小数
   sum[i]=prices[i]-min;
   //将计算总数转移到sum数组中
}
for(i=1;i<pricesSize;i++)
{
     max=fmax(max,sum[i]);
}
return max;
}`

当然这道题也可以跟上题一样用一个整型变量来记录，这里只是演示一下数组的记录。

例题3

这道题时利用哈希表的方法来解决的，但由于它的范围只有1-9，所以可以利用数组来记录，也就是动态规划转移的思路。但这道题相比前面的题目它从一维数组拓展到二维数组和三维数组。但思路其实是一致的。先分别建立三个数组来记录每个数的多少，将数组的小标对应数独数字的数-1即可。

将row[9]看成一个整体，由于一行有九列，所以是row[9],全部有九个数字，所以是row[9][9];col数组也是同样的道理。而subbox数组，由于是小宫格内看作一个数独，所以subbox[3][3]代表一个小宫格，全部有九个数字，所以是subbox[3][3][9]。理解这一步之后，后面也就简单起来了。

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
//通过建立数组来统计每一行，每一列，每小宫格是否超过1
int row[9][9];
int col[9][9];
int subbox[3][3][9];
//对数组进行初始化
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(subbox,0,sizeof(subbox));
for(int i=0;i<9;i++)
{
    for(int j=0;j<9;j++)
    {
        char c=board[i][j];//c为字符型不是整型
        if(c!='.')
        {
            int index=c-'0'-1;//index为数组的下标
            row[i][index]++;
            col[j][index]++;
            subbox[i/3][j/3][index]++;
            if(row[i][index]>1||col[j][index]>1||subbox[i/3][j/3][index]>1)
            {
                return false;
            }
        }
    }
}
return true;
}

这篇文章就先写到这里，如有错误请在评论区指正。