leetcode day10 动态规划篇 64+139

64 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

解题思路：动态规划题步骤

dp[i][j]表示到i行j列最小路径和

1、初始化，dp[i][j]=grid[i-1][j-1]

只有一条路径的，即图形左边缘和上边缘，初始化。

 dp[i][1]+=grid[j][0]

  dp[1][i]+=grid[0][j]

3、确定状态转移方程

dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j]

int min(int a,int b){
   if(a>b)return b;
   else return a;
}
int minPathSum(int** grid, int gridSize, int* gridColSize) {
    //m为行，n为列
    int m=gridSize,n=gridColSize[0];
    if(m==0||n==0)return 0;
    int dp[205][205]={};
    //初始化
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=grid[i-1][j-1];
        }
    }
    for(int i=2;i<=m;i++){
        for(int j=0;j<i-1;j++){
            dp[i][1]+=grid[j][0];
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<i-1;j++){
            dp[1][i]+=grid[0][j];
        }
    }
    //确定状态转移方程
     for(int i=2;i<=m;i++){
        for(int j=2;j<=n;j++){
            dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j];
        }
    }
    return dp[m][n];
}

139 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路：动态规划

dp[i]=1表示前i个来自字典,Size[i]为字典中第i个单词的长度

1、初始化 dp[0]=1,其他为0

2、确定状态转移方程

i从1开始，那么k=i-1+Size[j]

dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0)

strcmp与strncmp都是用来比较字符串的，区别在于能否比较指定长度字符串，故要多传一个长度参数。头文件为<string.h>

——举个例子 leetcode 字典为leet code

Size[0]=4,Size[1]=4

i=1,j=0,k=4,dp[4]=dp[0]&&strncmp(s,wordDict[0],Size[0]==0)=1

i=2,j=0,k=5,dp[5]=dp[1]&&strncmp(s+1,wordDict[0],Size[0]==0)=0

……

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[0],Size[0]==0)=0

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[1],Size[1]==0)=1

所以dp[8]=1=true

思考：如果字典中的单词不能重复使用，该怎么做

可以设个标记flag数组，如果字典第i个单词用过，即dp[k]=1时，标记flag[j]为1。

j循环中，当flag[j]==0时才使用下面的步骤

bool wordBreak(char * s, char ** wordDict, int wordDictSize){
   int len=strlen(s),i,j;
   if(wordDictSize==0)return 0;
   int Size[wordDictSize]={};
   for(i=0;i<wordDictSize;i++)Size[i]=strlen(wordDict[i]);
   //dp[i]=1表示前i个来自字典
   int dp[len+1];
   dp[0]=1;
   for(i=1;i<=len;i++)dp[i]=0;
   for(i=1;i<=len;i++){
      for(j=0;j<wordDictSize;j++){
         int k=i-1+Size[j];
         if(k>len)continue;
         dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0);
      }
   }
   return dp[len];
}